CS_alpha's blog

Why stable_sort() worked, but sort() didn't?
By CS_alpha, history, 15 months ago, In English

I used sort() in https://codeforces.me/contest/2056/submission/325199850 and got runtime error verdict, but used stable_sort() in https://codeforces.me/contest/2056/submission/325199048 and got accepted verdict.

Can someone please explain the reason? The rest of the code is unchanged.

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

Comments Comments (2)
| Write comment?
»
15 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Consider this test

5
00101
00101
11001
00001
11110

your comparator:

comp = [&bs,&n](int u, int v)  {
    if(v==u) return false;
    return bs[(u-1)*n+v-1]==0;
}

comp(2, 1) = true

comp(1, 2) = true

Which order is correct — 1<2 or 2<1? std::stable_sort will leave 2<1 (i think stable_sort would change the order of two elements if both comp(x, y) and comp(y, x) are true)

shuffling before sorting would ruin your solution

both comp(x, y) and comp(y, x) being true is UB. https://codeforces.me/blog/entry/72525

→ Reply