Cod sursa(job #1419794)

Utilizator stoianmihailStoian Mihail stoianmihail Data 16 aprilie 2015 15:57:46
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <string>
#include <stdio.h>
#include <iostream>
using namespace std;


int *AIB, *v, cp, m, maxim = 1, *clasament, step, certain;

void update(int val, int poz) {
    for(int i = poz; i <= maxim; i += (i & (-i)))
        AIB[i] += val;
}

int value(int poz) {
    int rez = 0;
    for(int i = poz; i > 0; i -= (i & (-i)))
        rez += AIB[i];
    return rez;
}

int find(int value) {
    int step = maxim, certain = -1;
    for(int j = 0; step; step >>= 1) {
        if(j + step < maxim && AIB[j + step] <= value) {
            if(AIB[j + step] == value) {
                certain = j + step;
                continue;
            }
            value -= AIB[j + step], j += step;
        }
    }
    return certain;
}

int main() {
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    int sol;
    scanf("%d", &m);
    for(cp = m; cp >>= 1; maxim <<= 1);
    maxim <<= 1;
    AIB = new int[maxim + 1];
    v = new int[m + 1];
    clasament = new int[m + 1];

    for(int i = 1; i <= m; ++i) {
        scanf("%d", &v[i]);
        update(1, i);
    }

    for(int i = m; i >= 1; --i) {
        sol = find(v[i]);
        update(-1, sol);
        clasament[sol] = i;
    }

    for(int i = 1; i <= m; ++i) {
        printf("%d\n", clasament[i]);
    }



    delete[] clasament;
    delete[] v;
    delete[] AIB;
    return 0;
}