Cod sursa(job #1239222)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 8 octombrie 2014 16:31:16
Problema Schi Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define nmax 30005

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

int n, i;
int V[nmax],R[nmax];
int ARB[2*nmax];

void build(int nod, int st, int dr)
{
    if (st == dr)
    {
        ARB[nod] = 1;
        return;
    }
    
    int mid = (st + dr) >> 1;
    
    if (st <= mid)
        build(2*nod, st, mid);
    if (mid < dr)
        build(2*nod+1, mid+1, dr);
    
    ARB[nod] = ARB[2*nod] + ARB[2*nod+1];
    
}

int query(int nod, int st, int dr, int val)
{
    ARB[nod]--;
    
    if (st == dr)
        return st;
    
    int mid = (st + dr) >> 1;

    if (ARB[2*nod] >= val)
        return query(2*nod, st, mid, val);
    else
        return query(2*nod+1, mid+1, dr, val - ARB[2*nod]);

}

int main()
{
    
    fin >> n;
    
    for (i=1; i<=n; i++)
        fin >> V[i];
    
    build(1, 1, n);
    
    for (i=n; i>0; i--)
        R[query(1, 1, n, V[i])] = i;
    
    for (i=1; i<=n; i++)
        fout << R[i] << "\n";
    
    fin.close();
    fout.close();
    
    return 0;
}