Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Undefined behavior when writing persistent segment tree

Revision en2, by ouuan, 2019-12-06 14:14:04

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ouuan 2019-12-06 14:14:04 4 Tiny change: '.\n\n2. Be aware of it' -> '.\n\n2. Beware of it'
en1 English ouuan 2019-12-06 14:09:21 2036 Initial revision (published)