I'm trying to solve this problem:

http://mirror.codeforces.com/problemset/problem/455/D

My submission:

http://mirror.codeforces.com/contest/455/submission/12009574

My algorithm runs in O(q * sqrt(n)) so it should pass the test cases. **So the question is:** what's wrong in my code to make it giving me TLE?

For n up to 1e5 and linear complexity you won't get TLE but you have no guarantee with O(n * sqrt(n)). Try to run custom invocation with some random input. Maybe constant is big and you need ~5s instead of 4s. Then you can change your code a bit.

I don't think that the problem with the big of constant, I tried different test cases with worst case and they gave me the answer with the specific time, and the previous test cases my code passed them all with less than 2s.

thanks for your help :)

`std::list`

can be very slow. Try replacing it with your own singly-linked list.Kinda obvious fix — picking proper constant for decomposition: 12011652

Upd.: This one looks even better — 12011711 :)Thank you very much, but just a question:

Is it needed every time to pick constant for decomposition or it was a special case for this problem?

Basically every decomposition solution does

C1 *root+C2 * (N/root) operations. Your goal is to minimize this value; will be best choise only ifC1 =C2, but in most cases one part of your solution is slower than other and you need to take a different value of root.Modulo Operator is very slow . Try Replacing

`from = ((from + lastans - 1) % N) + 1;`

to

Also Wherever you used modulo you should change it to this.