When I submit the program with the comparison function shown below, I get WA 27. But if I use a similar comparison function as bruce described in the other topic, i get AC. What's weird is that both result in the same answer (I assert-ed this), but maybe different permutations. So unless my evaluation function (also shown below) is wrong, the judge does not accept all valid permutations.

ll calc() {
    ll ca=0,cb=0,cc=0;
    REP(i,n) { ca+=x[i].a; cb=max(ca,cb)+x[i].b; cc=max(cb,cc)+x[i].c; }
    return cc;
}



typedef struct cmp2 {
    bool operator() (const X &x,const X &y) {
        return min(y.a+y.b,x.b+x.c)>min(x.a+x.b,y.b+y.c);
    }
} cmp2;

Edited by author 19.02.2007 05:37

I initially used exactly this function, but I realised that it's not a strict weak ordering: consider the toys 1 0 1, 1 0 2 and 2 0 1 (call them p, q, r). Then p === q (I use === to mean not less than or greater than), p === r, but q < r.

Can you tell me exactly how you formulated your function that was based on mine? Even after fixing an I/O problem I'm still getting WA #18 for this.

Hmmm, it is indeed not a strict weak ordering. I assumed it was, because http://ace.delos.com/OPEN06anal/mqueue.html says it is. (by the way, you wrote that. I should never trust you :P)

Anyway, that does not change the fact that both comparisons I use gave the correct final time (as assert-ed), but only one of the generated orderings is accepted. So either my evaluation function of an ordering is wrong, or the judge is wrong (I also assert-ed that each of the nr's was present in the final ordering, so it can't go wrong because stl assumes it is a strict weak ordering, I think).

Finally, my AC solution uses this:

typedef struct cmp1 {
    bool operator() (const X &x,const X &y) {
        return x.v<y.v;
    }
} cmp1;

and

    REP(i,n) { int p=x[i].a+x[i].b,q=x[i].b+x[i].c; x[i].v=p<q?p:INT_MAX-q; }

Yes, it was only during this contest I realised that the original comparator wasn't a strict weak ordering.

It appears that test case 18 exceeds the stated bounds on A, B and C, which was causing the problems. I now get AC using your comparison function (which is the same one I was trying during the contest, but I got screwed by the non-C99 printf.

I've also been screwed by that strange %I64d, as well as by the absence of <?=, >?=, __typeof and probably several others as well.