SmallGirl's blog

Bug C++?
By SmallGirl, history, 8 years ago, In English

Hi everyone, I was solving the problem from the recently ended contest May Circuits! https://www.hackerearth.com/may-circuits/algorithm/make-n00b_land-great-again-circuits/

But I faced a really strange problem! Here my AC submission: https://ideone.com/QxhGT6


// -----
	int hey = update2(l, r, x, (v == -1 ? -1 : t2[v].l), tl, tm);
	t2[now].l = hey;
	hey = update2(l, r, x, (v == -1 ? -1 : t2[v].r), tm + 1, tr);
	t2[now].r = hey;
// -----
 
 
/*	t2[now].l = update2(l, r, x, (v == -1 ? -1 : t2[v].l), tl, tm);
	t2[now].r = update2(l, r, x, (v == -1 ? -1 : t2[v].r), tm + 1, tr);*/

But if replace the first part with the second, even sample isn't working! I really need your help.

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

My guess is that in this line:

t2[now].l = update2(l, r, x, (v == -1 ? -1 : t2[v].l), tl, tm);

the order of evaluation is the following:

auto& tmp = t2[now];
auto val = update2(l, r, x, (v == -1 ? -1 : t2[v].l), tl, tm);
tmp.l = val;

Because update2 function adds elements to the vector t2, reallocation happens and tmp no longer points to a valid location.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you! I think I understood my problem! :) I really appreciate it!

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it 
http://acm.math.spbu.ru/~kunyavskiy/cpp/sol16.cpp
http://acm.math.spbu.ru/~kunyavskiy/cpp/
→ Reply