Neutralised's blog

Need some help about CF498B
By Neutralised, history, 2 years ago, In English

Link to the problem

Link to my submissions
(The topmost submissions are for this problem. There are several coding styles because my teammate asked me to give an implementation in his coding style so that he can help me debug more comfortably XD)

All of my submissions got TLE on test #65, However, I don't know why.
After trying several times, I made a datamaker: 

#include <bits/stdc++.h>
using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
main(){
	const int n=5000; puts("5000 5000");
	for(int i=1;i<=n;++i)
		printf("%d %d\n",49+(rnd()&1),rnd()%10+1);
}

and uses my teammate's solution to check with mine. (In fact, my fastest submission runs faster than his offline)

After many tests I knew that my solution is correct because no WA. Then I outputted the running time of it and see if it got TLE offline. But unfortunately not(. Below is the result:

(Idk whether you can see this picture. It's showing that I've passed 5300 tests generated by my datamaker offline and none of these tests got TLE. The longest time cost is about 0.6s.)

I've changed all names of variables and arrays that may cause Undefined Behavior (as far as my teammate and I know).
Can anyone tell me why it still got TLE on codeforces? Thanks very much!!!!!!!

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

»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

You can pass test 65 with I/O optimization, and then fail at 69 XD.

Edit: It actually got past that test because of C++20 and not the I/O optimizations.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thks.
    I just tried opening $$$\text{O2}$$$ mode and choose C++20 and then passed all tests...
    I think it's quite interesting.
    (But I used neither C++20 nor $$$\text{O2}$$$ on my computer when checking, so why I got TLE on CF is still a mystery lol)

    Upd：I guess that test #69 is all like 30 5000, and just tested it offline, only takes 0.2s to output the answer. Strange I think(

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      It might be because your CPU can do much better than it's allowed on CF.

      For example, if your CPU can do 1 billion operations per second and CF limits 100 million per second, your PC will have ~10x better results time-wise.

      → Reply