Блог пользователя lequydon

Автор lequydon, история, 15 месяцев назад, По-английски

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

My first submission is: https://mirror.codeforces.com/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://mirror.codeforces.com/problemset/submission/547/303635252

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
15 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.