OptimalKnight's blog

By OptimalKnight, history, 3 years ago, In English

The codeforces round #742 has recently ended, and I cannot understand why the brute force solutions of problem B are not giving TLE on system testing. We require the Xor values of the range [0,1,2,...,a-1], where a<=3e5 for 5e4 test cases. The Editorial says that Xor values can be precomputed in O(n) time, and then the test cases can be answered in O(1) time. Still, I have seen many submissions who have calculated these range Xor values individually for every test case and still didn't get TLE. Isn't the overall complexity for this operation supposed to be O(t*a)? Which is roughly around O(15e9) or O(1e10). I saw someone saying it got AC because of 'Pragmas'. Pragmas or not. Shouldn't 1e10 give TLE? Are Pragmas these powerful, or is there something I'm missing? Ps: I myself got AC using the said Brute Force, but I resubmitted thinking it would give TLE on system testing.

Full text and comments »

  • Vote: I like it
  • +44
  • Vote: I do not like it