Yesterday, investigating Strange TLE by cin using GNU C++20 (64), I found an easy and reproducable way to trigger a slowdown bug that I believe has been plaguing Codeforces for some time now. So I'm making this blog to raise awarness of it. MikeMirzayanov, please take a look at this!
Here is how to trigger the slowness bug:
- Take any problem with a relatively large input on Codeforces ($$$2 \cdot 10^5$$$ ints is enough).
- Take a random AC C++ submission that uses
std::cin. - Add the line
vector<vector<int>> TLE(40000, vector<int>(7));somewhere in global space. - Submit using either C++20(64 bit) or C++17(64 bit).
- ???
- TLE
For example take tourist's solution to problem 1936-D - Битовый парадокс. With the vector of death added to the code, it gets TLE on TC5 (taking $$$> 5$$$ s). While without the deadly vector, the submission takes 155 ms on TC5.
Here is a stand alone example with the slowdown (credit to kostia244). It runs 100 times slower with the vector.
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> TLE(40000, vector<int>(7));
int main() {
string s;
for(int i = 0; i < 17; i++) s += to_string(i) + " ";
for (int j = 0; j < 60000; ++j) {
istringstream ss(s);
int x;
while (ss >> x);
}
}
What is causing this?
Background
