Hi, if you compare this submission (296ms) with this one (3025ms), this is the difference:
I think this is crazy because g is a vector<vector<int>> with size 3 * 10^5 with at most 3 * 10^5 entries, and the function build that returns g is called once in the program. This huge time difference is the same on both 64-bit C++ compilers, but it is not present in the 32-bit C++ compiler.
UPD: Calling the function build twice solves the problem
Auto comment: topic has been updated by wnmrmr (previous revision, new revision, compare).
Looks like the problem is in tuple. Removed it and got 300 ms: link
Would be nice to know, why it happens.
The output of build() in the "good" version is immediately cast to the tuple, while the "bad" version performs some expensive type conversions. Just look at the disassembly using GDB.
Auto comment: topic has been updated by wnmrmr (previous revision, new revision, compare).
So $$$x = 3000$$$ and $$$2x = 300$$$? Hmm...
Probably that particular version of compiler doesn't handle captures of structured bindings well.
Though I tried to pass it as a parameter instead and it didn't help. Then simply accessing
gmust be slow.This is my guess too, that somehow that test case makes cache funky when acessing
g. Looks like if you callbuild(s)an odd number of times, it is fast, but if you call it an even number of times, it is slow again, so there must be something strange withg's memory offset.