dcordb's blog

My solution gets TLE on 712D (Memory and Scores)
By dcordb, history, 10 years ago, In English

Hi everyone. My solution to problem 712D gets TLE, even though its complexity is . Where d is the difference between the score of Memory and Lexa. Note that  - 2·105 ≤ d ≤ 2·105.

The funny thing is that in my laptop (Intel Core i5, 4gb ram) my solution runs in 1.2s. What do you think about this, is CF that slow? Anyway could you help me?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

You solution runs too slow because of dozens of modulo operations.
Try to use:

if (some_variable >= MOD)
    some_variable -= MOD;

As for second part of the question, I don't understand either why it's so slow on CF servers. My laptop also runs in 1.1s (compiled g++ -O2).

→ Reply