Hello codeforces! I've come to ask help in a time of great mystery.

I was helping to debug a problem where the code would pass the 2s TL when on a 64-bit compiler but would get confortably under 1s on a 32-bit one when some really bizarre things started to happen.

First, pinning down where the problematic parts were, it turns out this was the thing consuming practically the whole time limit:

set<ll> s;
for (int i(0); i < k; ++i) {
    int pp;
    cin >> pp;
    s.insert(pp);
}

Im not joking. Also k <= 3e5 btw.

It really shouldnt be a big deal, and normally that part should take less than 140ms, but both on C++20 (64) and C++17 (64) make it take from 1900ms to 2000ms.

I made a submission that outputs the time taken to do the input, the inserting, and the ammount of elements in the set; and with that even more weird stuff appears. Look at the result:

142730404

0:
Input Time: 0ms
Insert Time: 0ms
Set Size: 0

50000:
Input Time: 36ms
Insert Time: 38ms
Set Size: 50000

100000:
Input Time: 74ms
Insert Time: 83ms
Set Size: 99904

150000:
Input Time: 566ms
Insert Time: 142ms
Set Size: 99904

200000:
Input Time: 1059ms
Insert Time: 200ms
Set Size: 99904

250000:
Input Time: 1543ms
Insert Time: 244ms
Set Size: 99904

In this test case until the 90000-ish iteration there are distinct elements and after that the input time starts to raise aggressively, while the insert time grows at a basically unaltered pace. Maybe they start repeating a relatively big number, but even then, it goes from 30ms to read 50000 guys to 500ms. It's insane.

If you want, take a look at the version of the output when using 32-bit for comparison (the numbers will actually be a bit inflated because you need to get the timings with std::chrono):

142730436

0:
Input Time: 0ms
Insert Time: 0ms
Set Size: 0

50000:
Input Time: 41ms
Insert Time: 47ms
Set Size: 50000

100000:
Input Time: 82ms
Insert Time: 101ms
Set Size: 99904

150000:
Input Time: 123ms
Insert Time: 151ms
Set Size: 99904

200000:
Input Time: 164ms
Insert Time: 198ms
Set Size: 99904

250000:
Input Time: 204ms
Insert Time: 240ms
Set Size: 99904

Final Input Time: 245ms
Final Insert Time: 285ms
Final Set Size: 99904

Ending thoughts

• The problematic test case is case 6, however case 5 has the same input size and the set ends up with more items (see 142732612). Why is the problem only with test 6???

• If instead of reading a variable and instantly inserting it into the set, you first input an array and then insert it into the set, no tragedy happens (142732784).

• How can the input go so wrong? A 20x slowdown out of nowhere should not be happening.

• Is there a way to get the raw test data from the authors or something similar to see what actually was on test 6 so we can try to replicate it?

• Thanks qwexd for doing nothing.