Cod sursa(job #2116204)

Utilizator ioana_marinescuMarinescu Ioana ioana_marinescu Data 27 ianuarie 2018 13:26:13
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
const int MAX_N = 30005;
const int MAX_ARB_INT_N = 1 << 16;

using namespace std;

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

int n, a[MAX_N], arbInt[MAX_ARB_INT_N], sol[MAX_N];

void build(int nod, int st, int dr, int index)
{
    int mij;
    if(st==dr)
        arbInt[nod]=1;
    else {
        mij=(st+dr)/2;
        if(index<=mij)
            build(2*nod, st, mij, index);
        else
            build(2*nod+1, mij+1, dr, index);
        arbInt[nod]=arbInt[2*nod]+arbInt[2*nod+1];
    }
}

void query(int nod, int st, int dr, int index, int value)
{
    int mij;
    if(st==dr) {
        arbInt[nod]=0;
        sol[st]=index;
    }
    else {
        mij=(st+dr)/2;
        if(value<=arbInt[2*nod])
            query(2*nod, st, mij, index, value);
        else
            query(2*nod+1, mij+1, dr, index, value-arbInt[2*nod]);
        arbInt[nod]=arbInt[2*nod]+arbInt[2*nod+1];
    }
}
int main()
{
    int i;
    fin>>n;
    for(i=1; i<=n; i++) {
        fin>>a[i];
        build(1, 1, n, i);
    }
    for(i=n; i>=1; i--)
        query(1, 1, n, i, a[i]);
    for(i=1; i<=n; i++)
        fout<<sol[i]<<'\n';
    return 0;
}