The idea of the mentioned paradox is not new, online articles discuss this referencing a paper from 1965 by Michael Scriven ("An essential unpredictability in human behaviour.") and is called "Scrivens paradox". It has already several answers.
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 both calculate the future truly and reveal it ahead of time.
That alone refutes the idea of disproving determinism by logic alone.
The intuition that in a deterministic universe perfect knowledge means predictability can be found as Laplace's demon, and it is also refuted, though artificial systems can be both fully deterministic and predictable from the outside, some even from the inside.
As a side-note: even with perfect knowledge in a purely deterministic universe, not all futures are necessarily computable. E.g. see Undecidable_problem. But that's just yet another reason such a machine cannot be built, not the main reason such a prediction is impossible.
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), so any source of random does not matter for the discussion. A third alternative, something that is neither determined nor random but "intentional" is regarded as philosophically nonsensical by mainstream philosophy, but still upheld by religions.
Mini-Universe Example
Even without considering the issue of predictability not being granted in determinism due to undecidability, a simple example can show the logical problem of predicting a future that is influenced by the prediction:
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 both produce and reveal.
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.
Special circumstances
This is different in fatalism and predeterminism, in which a machine could be built that predicts the future and the human cannot do the opposite, prevented by the determined future from doing the opposite.
But that's not the same as determinism, and not a popular modern belief. It's a misconception of determinism by dualists, sometimes used as straw man to dismiss monism or physicalism.