Cod sursa(job #1106250)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 12 februarie 2014 17:53:36
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<fstream>
using namespace std;

int N,v[30010],maxarb[30010*4],sol[30010],poz,val;

void citire() {

    ifstream in("schi.in");
    int i;
    in>>N;
    for(i=1;i<=N;i++)
        in>>v[i];
    in.close();

}

void update(int nod, int st, int dr) {

    int mij;
    if(st==dr) {
        maxarb[nod]=val;
        return;
    }
    mij=(st+dr)/2;
    if(poz<=mij)
        update(2*nod,st,mij);
    else
        update(2*nod+1,mij+1,dr);

   maxarb[nod]=maxarb[2*nod+1]+maxarb[2*nod];

}

int query(int Nod,int st,int dr,int Val) {

    int mij;
    if(st==dr)
        return st;
    mij=(st+dr)/2;
    if(Val<=maxarb[2*Nod])
        return query(2*Nod,st,mij,Val);
    else
        return query(2*Nod+1,mij+1,dr,Val-maxarb[2*Nod]);

}


void solve() {

    int i,a;
    for(i=1;i<=N;i++) {
        poz=i;
        val=1;
        update(1,1,N);
    }

    for(i=N;i>=1;i--) {
        a=query(1,1,N,v[i]);
        sol[a]=i;
        poz=a;
        val=0;
        update(1,1,N);
    }

}

void afisare() {

    ofstream out("schi.out");
    int i;
    for(i=1;i<=N;i++)
        out<<sol[i]<<'\n';
    out.close();

}

int main() {

    citire();
    solve();
    afisare();
    return 0;

}