CS_alpha's blog

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

I used sort() in https://mirror.codeforces.com/contest/2056/submission/325199850 and got runtime error verdict, but used stable_sort() in https://mirror.codeforces.com/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

»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by CS_alpha (previous revision, new revision, compare).

→ Reply
»
10 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://mirror.codeforces.com/blog/entry/72525

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it -9 Vote: I do not like it

    Get it.

    Maybe you help me debug and solve a problem in future contests.

    → Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thanks. Now I fixed it.
    ~~~~~
    sort(all(aa),[&bs,&n](int u, int v) {
    if(u<v){
    if(bs[(u-1)*n+v-1]) return true;
    else return false;
    }else{
    if(bs[(u-1)*n+v-1]) return false;
    else return true;
    }
    });
    ~~~~~

    → Reply