Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Think you can solve it :)? We all know it is expected that contradictory comparison functions may cause Runtime Error when used by the sort method. For instance, one could try sorting an array using a function that only returns True!

However, when seemingly equivalent procedures start giving different results, curiosity strikes!
Take this example:

struct number{
    int z;
    const bool operator< (const number &that) const{
        return z <= that.z;
    }
}numbers[10000];

int main (){
    for(int i = 0; i < 10000; i++){
        numbers[i].z = 2;
    }
    sort(numbers, numbers+10000);
    return 0;
}

Note the operator< returns <=. In some cases this would cause a Runtime Error, such as if you replaced the
"numbers[i].z = 2;" line with something like "numbers[i].z = i%10;". But we will focus on this case, on which it does not result in error.

By now you must've noticed this struct basically simulates the sorting of an integer array, except for the <= comparison. So, one would expect an int array to behave similarly, when using a similar comparison function! Yet...

int array[10000];
const bool myfunc (int a, int b){
    return a <= b;
}

int main (){
    for(int i = 0; i < 10000; i++){
        array[i] = 2;
    }
    sort(array, array+10000, myfunc);
    return 0;
}

If you try to execute this piece of code, although it inherently seems to be doing exactly the same as the one above, a Runtime Error will occur this time. Can you guess why? :)

Full text and comments »

Oi.'s blog