20121030_problem1

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define ATHLETES_MAX_NUMBER 200000

struct athlete {
    int weight, strength, number;
};

void swap(athlete * a, athlete * b) {
    athlete t = *a;
    *a = *b;
    *b = t;
}

int n, curWeight, curStrength, ans, result[ATHLETES_MAX_NUMBER], weightsSum;
athlete athletes[ATHLETES_MAX_NUMBER];

void sort(int l, int r) {
    int i = l, j = r, mediane = l + rand() % (r - l + 1), weightMediane = athletes[mediane].weight, strengthMediane = athletes[mediane].strength;
    do {
        while (athletes[i].weight < weightMediane || athletes[i].weight == weightMediane && athletes[i].strength < strengthMediane) ++i;
        while (athletes[j].weight > weightMediane || athletes[j].weight == weightMediane && athletes[j].strength > strengthMediane) --j;
        if (i <= j) {
            swap(athletes + i, athletes + j);
            ++i;
            --j;
        }
    } while (i <= j);
    if (l < j) sort(l, j);
    if (i < r) sort(i, r);
}

int main() {
    srand(time(NULL));
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &curWeight, &curStrength);
        athletes[i].weight = curWeight;
        athletes[i].strength = curStrength;
        athletes[i].number = i + 1;
    }
    sort(0, n - 1);
    weightsSum = 0;
    for (int i = 0; i < n; ++i)
        if (athletes[i].strength >= weightsSum) {
            result[ans++] = athletes[i].number;
            weightsSum += athletes[i].weight;
        }
    printf("%d\n", ans);
    for (int i = ans - 1; i >= 0; --i)
        printf("%d ", result[i]);
    return 0;
}