Cod sursa(job #951162)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 19 mai 2013 16:54:23
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<fstream>
using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

const int MAXN = 30010;
int N, rez[MAXN], arb[3*MAXN], rez1[MAXN], poz;

void update(int p, int st, int dr, int val)
{
    if(st == dr)
    {
        arb[p] = val;
        return;
    }
    int mid = (st + dr)/2;
    if(poz <= mid)
        update(2*p, st, mid, val);
    else
        update(2*p+1, mid+1, dr, val);
    arb[p] = arb[2*p] + arb[2*p+1];
}

void query(int p, int st, int dr, int value)
{
    if(st == dr){
        poz = st;
        return;
    }
    int mid = (st + dr)/2;
    if(value <= arb[2*p])
        query(2*p, st, mid, value);
    else
        query(2*p+1, mid+1, dr, value-arb[2*p]);
}

int main()
{
    int i, aux;
    fin >> N;
    for(i=1; i<=N; ++i){
        fin >> rez[i];
        poz = i;
        update(1, 1, N, 1);
    }

    for(i=N; i>0; --i)
    {
        query(1, 1, N, rez[i]);
        rez1[poz] = i;
        update(1, 1, N, 0);
    }

    for(i=1; i<=N; ++i)
        fout << rez1[i] << "\n";

    fin.close();
    fout.close();

    return 0;
}