In other words, we are looking for polynomials $P$ such that $\left\lfloor P(x)\right\rfloor$ is constant on $[\sqrt{n},\sqrt{n+1})$ and such that $\lfloor P(x)\rfloor=\lfloor P(-x)\rfloor$. In particular, $\deg P$ must be even. In particular $P(\sqrt{n})$ and $P(\sqrt{n+1})$ differ by at most $1$ which already shows that $\deg P \le 2$ since any polynomial of higher degree grows too quickly for large $n$. Clearly any constant polynomial satisfies the condition. From now on we assume that $P(x)=ax^2+bx+c$ is a quadratic polynomial with $a \ne 0$. Since $\lfloor P(x)\rfloor=\lfloor P(-x)\rfloor$ we have $\vert P(x)-P(-x)\vert \le 2$ for all $x$ and hence $b=0$. So $P(x)=ax^2+c$. So with $Q(x)=P(\sqrt{x})=ax+c$ the condition is that $\lfloor Q(x)\rfloor$ is constant on $[n,n+1)$ for $n \in \mathbb{N}$. In particular $Q(x)$ takes integer values at $x>0$ only if $x \in \mathbb{Z}$. This also shows that $a>0$ since otherwise $\lfloor Q(x)\rfloor \ne \lfloor Q(x+\varepsilon)\rfloor$ for such $x$. So for all large integers $n$, there is some $x_n \in \mathbb{N}$ such that $ax_n+c=n$. Hence $a(x_{n+1}-x_n)=1$ so that $a=\frac{1}{m}$ for some $m \in \mathbb{N}$. Hence $x_n=mn-mc$ so that $c=\frac{k}{m}$ for some integer $k$. So $P(x)=\frac{x^2+k}{m}$ for integers $k,m$ with $m>0$. And indeed, any such polynomial satisfies the condition with $a_n=\left\lfloor \frac{n+k}{m}\right\rfloor$. So all the solutions are the constant polynomials and the polynomials $P(x)=\frac{x^2+k}{m}$ with integers $k,m$ and $m>0$.