lequydon's blog

Why Runtime error?
By lequydon, history, 11 hours ago, In English

I was working on this problem: https://codeforces.me/problemset/problem/547/B

My first submission is: https://codeforces.me/problemset/submission/547/303635124

This code resulted runtime error on test 49

However, when I removed the equal sign in my comparator function:

bool cmp(int x, int y){ return a[x] <= a[y]; }

My new submision is: https://codeforces.me/problemset/submission/547/303635252

The code was accepted! Can anyone explain why this change made a difference? Thanks!

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

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

I'm pretty sure that sort function needs a strict ordering on the elements.

→ Reply
  • »
    »
    10 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    If you just run this code

    int main(){
    vector<long long> v(100000,42);
    sort(v.begin(),v.end(),[](int a, int b){return a<=b;});
    for (int i=0;i<v.size();i++) cout << v[i] << " ";
    cout << '\n';
    return 0;
}

    There are some incorrect values at the beginning of the array sometimes, looks like the implementation of the sorting function relies on the ordering being strict, otherwise it can be undefined. I stumbled upon this some time ago when using a custom comparison on a set. I think the way they establish whether two elements are equal is that !(a < b) && !(b < a) => a = b. This wouldn't work for your comparison — there could be something similar in sorting function.

    → Reply
»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

The return value of the function call operation applied to an object of a type satisfying Compare, when converted to bool, yields true if the first argument of the call appears before the second in the strict weak ordering relation induced by this type, and false otherwise.

Took this from cppreference. You can read the full Compare requirement here.

→ Reply
»
9 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

In C++, comparator should return false if its arguments are equal

→ Reply