Cod sursa(job #1800932)

Utilizator penetavyPene Cosmin-Octavian penetavy Data 8 noiembrie 2016 13:33:12
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <algorithm>

#define N_MAX 30000
#define aib_size 32768

using namespace std;

FILE *fin = fopen("schi.in", "r");
FILE *fout = fopen("schi.out", "w");

int N;
int aib[aib_size + 1];
int v[N_MAX + 1];

void add(int pos, int val) {
    do {
        aib[pos] += val;
        pos += pos & (-pos);
    } while (pos <= aib_size);
}

int cautBin(int val) {
    int x = 0;
    int pas = aib_size / 2;
    while (pas) {
        if  (aib[x + pas] < val) {
            val -= aib[x + pas];
            x += pas;
        }
        pas >>= 1;
    }
    return x + 1;
}

void init() {
    int i;
    for (i = 1; i <= aib_size; i++)
        aib[i] = i & (-i);
}

struct anakin {
    int nr, place;
};

anakin participant[N_MAX + 1];

bool cmp(anakin a, anakin b) {
    if(a.place > b.place)
        return false;
    return true;
}

int main(){
    int i, j;
    int pos;

    fscanf(fin, "%d", &N);
    for (i = 1; i <= N; i++)
        fscanf(fin, "%d", &v[i]);

    init();

    for (i = N; i >= 1; i--) {
        pos = cautBin(v[i]);
        add(pos, -1);
        participant[i].nr = i;
        participant[i].place = pos;;
    }

    sort(participant + 1, participant + N + 1, cmp);

    for (i = 1; i <= N; i++)
        fprintf(fout, "%d\n", participant[i].nr);

    fclose(fin);
    fclose(fout);
    return 0;
}