View Code of Problem 1094

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 222222;

struct Cow{
    int rank, score, aid;
};
Cow c_aid[maxn], c_score[maxn];
int N, C, F;

bool cmpa(Cow & i, Cow & j) {
    return i.aid < j.aid;
}

bool cmps(Cow & i, Cow & j) {
    return i.score < j.score;
}

int main() {
    while(~scanf("%d%d%d", &N, &C, &F)) {
        for(int i = 0; i < C; i++)
            scanf("%d%d", &c_score[i].score, &c_score[i].aid);
        sort(c_score, c_score+C, cmps);
        for(int i = 0; i < C; i++)
            c_score[i].rank = i;
        memcpy(c_aid, c_score, sizeof(Cow)*C);
        sort(c_aid, c_aid+C, cmpa);
        int L = 0, R = C, ans = -1;
        while(R-L > 1) {
            int mid = (L+R)>>1;
            int left = 0, right = 0, tot = c_score[mid].aid;
            for(int i = 0; i < C; i++) {
                if((c_aid[i].rank < mid) && (tot+c_aid[i].aid <= F) && (left < N/2)) {
                    tot += c_aid[i].aid;
                    left++;
                }
                else if((c_aid[i].rank > mid) && (tot+c_aid[i].aid <= F) && (right < N/2)) {
                    tot += c_aid[i].aid;
                    right++;
                }
            }
            if(left < N/2 && right < N/2) {
                ans = -1;
                break;
            }
            else if(left < N/2) L = mid;
            else if(right < N/2) R = mid;
            else ans = c_score[mid].score, L = mid;
        }
        printf("%d\n", ans);
    }
    return 0;
}

/*
In file included from algorithm:62,
                 from F:\temp\16139852.54869\Main.cc:4:
stl_algo.h: In function 'const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&, _Compare) [with _Tp = Cow, _Compare = bool (*)(Cow&, Cow&)]':
stl_algo.h:2301:   instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = Cow*, _Size = int, _Compare = bool (*)(Cow&, Cow&)]'
stl_algo.h:5258:   instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = Cow*, _Compare = bool (*)(Cow&, Cow&)]'
F:\temp\16139852.54869\Main.cc:27:   instantiated from here
stl_algo.h:124: error: invalid initialization of reference of type 'Cow&' from expression of type 'const Cow'
stl_algo.h:125: error: invalid initialization of reference of type 'Cow&' from expression of type 'const Cow'
stl_algo.h:127: error: invalid initialization of reference of type 'Cow&' from expression of type 'const Cow'
stl_algo.h:131: error: invalid initialization of reference of type 'Cow&' from expression of type 'const Cow'
stl_algo.h:133: error: invalid initialization of reference of type 'Cow&' from expression of type 'const Cow'
*/