Today, I spent a whole afternoon solving 786C - Till I Collapse, because of undefined behavior.
The origin code is here: 66394911. It seems pretty well, but can't even pass the sample tests.
However, after adding one line (t.reserve(5000000);) it passed: 66394938.
For those who don't want to read my codes, here is a shorter one:
#include <iostream>
#include <vector>
using namespace std;
vector<int> bar;
int foo(int p)
{
int x = bar.size();
bar.push_back(bar[0]);
if (p == 0) return x;
bar[x] = foo(p - 1);
cout << bar[x] << ' ';
return x;
}
int main()
{
bar.resize(1, 0);
foo(5);
return 0;
}
Can you guess the output?
The output
The reason
Some notes:
x.emplace_back(x[0]), orauto& stored_reference = ...; modify();._GLIBCXX_DEBUGcurrently. However, iterator invalidation can be prevented.auto tmp = foo(p - 1); bar[x] = tmp;this "bug" is fixed with c++17, the order of evaluation is specified to be first the right side of the assignment then the left (as you would probably expect it).