Even with perfect knowledge in a purely deterministic universe, not all futures are computable. E.g. see Undecidable_problem
So it's not merely practically impossible to build a perfect predictor for such cases. The existence of a so called "Counter", something that would use the prediction to do the opposite, makes it logically impossible to calculate the future in that situation.
If it were logically possible in theory to create a prediction in such a situation, determinism could not logically be true. Since such a prediction is logically impossible, it's concept does not logically make determinism impossible.
The idea of the mentioned paradox is not new, online articles discuss this referencing a paper from 1968 by Michael Scriven and is called "Scrivens paradox". Wikipedia has no article on this, i might just start one.
The intuition that in a deterministic universe perfect knowledge means predictability can be found as Laplace's demon
Mainstream philosophy holds that likely our universe is not 100% deterministic, but free will would still be possible even if it was 100% deterministic (Compatibilism).
To give a more detailed argument in why determinism does not imply predictability: there are known computational problems known and proven to be undecidable, proven that it's logically impossible to find a solution in finite time. If the inanimate future (without humans) was predictable by a machine, we could use such a machine to predict the outcome of computing such a problem within finite time, thus having achieved the impossible.
We can imagine a closed system of a rock dropping down a tube, a gate that can be open or shut, and a computer predicting the future, and another computer acting as the Anti, like in the image above. Since the gate is open, the predictor predicts the rock will drop to position A. The Anti, seeing the prediction, shuts the gate, so the rock wont drop to A but be stuck at B. The predictor could anticipate that, and predict B, but that would just make the Anti choose to keep the gate open, so that prediction would also fail.
This system has no humans, no "free will" in a sense breaking determinism, no random, no quantum effects or other aspects preventing perfect knowledge. Yet a true prediction is impossible for the predictor machine to produce.
If such a device was built, it would be perfectly predictable from the outside, it would be possible to truly predict that either the rock ends up where predicted or not, but the predictor in the system could not logically predict that.
The Anti has free will in the sense that it can prevent each prediction, but it's so simple that we don't even need a computer to build it, it can be a purely mechanical device, same as the predictor.
This demonstrates that the human ability to choose a different outcome than a prediction does not disprove determinism and does not even elevate us above inanimate matter.