For every prime $p$, does there exists integers $x\_1$, $x\_2$ and $x\_3$ ($0\leq x\_1, x\_2, x\_3 \leq \lfloor cp^{1/3}\rfloor$ and $c$ is some large constant) such that $\frac{p-1}{2}-\lfloor 2cp^{1/3} \rfloor \leq f(x\_1,x\_2,x\_3) \leq \frac{p-1}{2}$, where, $f(x\_1,x\_2,x\_3)=x\_1+x\_2+x\_3+2(x\_1x\_2+x\_2x\_3+x\_3x\_1)+4x\_1x\_2x\_3$.



Integer solution
I doubt that the lower bound $\frac{p-1}{2} - 2cp^{1/3}$ holds for all $p$. Here is a proof for the weaker bound $\frac{p-1}{2} - cp^{1/2}$. 


First of all, the inequality $\frac{p-1}{2}-cp^{1/2} \leq f(x\_1,x\_2,x\_3) \leq \frac{p-1}{2}$ is essentially equivalent to
$$p- O(p^{1/2}) \leq (2x\_1+1)(2x\_2+1)(2x\_3+1) \leq p.$$


Let us take $y=\left\lceil\frac{p^{1/3}-1}{2}\right\rceil$. Then 
$$p \leq (2y+1)^3 < (p^{1/3}+2)^3 < p + O(p^{2/3}).$$


Define 
$$z = \left( \frac{(2y+1)^3 - p}{4(2y+1)} \right)^{1/2} .$$
Clearly, we have $z=O(p^{1/6})$.


Now, let us take $x\_1 = y$, $x\_2 = y - \lceil z\rceil$, $x\_3 = y + \lceil z\rceil$ so that
$$(2x\_1+1)(2x\_2+1)(2x\_3+1) = (2y+1)^3 - 4\lceil z\rceil^2(2y+1)$$
$$ < (2y+1)^3 - 4z^2(2y+1) = p.$$
On the other hand, we have
$$(2x\_1+1)(2x\_2+1)(2x\_3+1) = (2y+1)^3 - 4\lceil z\rceil^2(2y+1) $$
$$ > (2y+1)^3 - 4(z+1)^2(2y+1) = p - O(p^{1/2}).$$


