2169D2 - Removal of a Sequence (Hard Version)

Here is an implementation of $$$O(\sqrt{A} \cdot \log{A})$$$ (where $$$A = 10^{12}$$$) solution from the beginning of editorial for this problem: 349377703.

It works in $$$10.5$$$ seconds on current testset and was intended to be too slow to pass: the expected complexity is $$$O(\sqrt{A})$$$.

But after some optimizations I was able to speed it up x6.5 times down to $$$1.64$$$ seconds and get AC: 349377750

Optimizations are:

• Usage of reciprocal multiplication for division on $$$y$$$

• Usage of reciprocal multiplication for division on small (up to $$$2^{21}$$$) numbers

• If-else checking for very small (up to $$$3$$$) result of division

Can someone hack it? Or maybe speed it up even more?

Hello codeforces community!

Since I already have top-2000 and top-200 t-shirts from previous participations and because I don't wanna spent another ~40$ to get it delivered to Russia (especially with current ruble situation :/) I decided to give it to the first person who will hack my solution to the Shortest Routes I problem from CSES.

The solution is based on SPFA algorithm which in theory could run in $$$O(nm)$$$ as Ford-Bellman does, but in practice it is quite fast, sometimes even faster then Dijkstra.

Give it a try!

UPD: Faisal-Saqib was the the first to hack, congratulations! Sent you the code in DMs.