Cod sursa(job #992661)

Utilizator harababurelPuscas Sergiu harababurel Data 2 septembrie 2013 12:25:31
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <iostream>
#include <fstream>
#define nmax 30005
using namespace std;

int v[nmax], H[2*nmax+100], p[nmax];
int n, sol;

void query(int node, int lo, int hi, int pos) {
    if(lo == hi) {
        sol = lo;
        return;
    }

    int mid = (lo + hi) >> 1;
    if(pos <= H[2*node]) query(2*node, lo, mid, pos);
    else                 query(2*node+1, mid+1, hi, pos - H[2*node]);

}

void update(int node, int lo, int hi, int pos, int val) {
    if(lo == hi) {
        H[node] = val;
        return;
    }

    int mid = (lo + hi) >> 1;
    if(pos <= mid) update(2*node, lo, mid, pos, val);
    else           update(2*node+1, mid+1, hi, pos, val);

    H[node] = H[2*node] + H[2*node+1];
}


int main() {
    ifstream f("schi.in");
    ofstream g("schi.out");

    f>>n;
    for(int i=1; i<=n; i++) f>>v[i], update(1, 1, n, i, 1);

    for(int i=n; i>=1; i--) {
        query(1, 1, n, v[i]);           //gasesc a v[i]-a pozitie ramasa libera
        update(1, 1, n, sol, 0);        //si o transform in 0

        p[sol] = i;
    }
    for(int i=1; i<=n; i++) g<<p[i]<<"\n";

    return 0;
}