Cod sursa(job #1855925)

Utilizator hasmasandragosHasmasan Dragos hasmasandragos Data 24 ianuarie 2017 13:09:12
Problema Schi Scor 100
Compilator cpp Status done
Runda gym_emag_avansati_2016 Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");

int arb[4*30020],n,v[30005],final[30005],pozitie,i,j,aux;

void build (int st , int dr , int nod )
{
    int mij;
    mij=(st+dr)/2;
    if (st==dr)
    {
        arb[nod]=1;
        return ;
    }
    build (st,mij,2*nod);
    build (mij+1,dr,2*nod+1);
    arb[nod]=arb[nod*2]+arb[nod*2+1];
}

void query (int st , int dr ,int nod , int rest )
{
    int mij;
    if (st==dr)
    {
        arb[nod]=0;
        pozitie=st;
        return;
    }
    mij=(st+dr)/2;
    if (rest<=arb[2*nod]) // vedem daca mergem in stanga sau in dreapta
     query(st,mij,2*nod,rest);
    else
     query(mij+1,dr,2*nod+1,rest-arb[2*nod]);
    arb[nod]=arb[nod*2]+arb[nod*2+1];
}

int main()
{
    f>>n;
    for (i=1;i<=n;i++)
      f>>v[i];
    build(1,n,1);
    for (i=n;i>=1;i--)
    {
        query(1,n,1,v[i]); // in loc sa luma toati concurentii in ordinea in care vin , ii luam in ordine inversa si vedem pentru concurentul i , a cata pozitie neeliminata ii corespunde
        final[pozitie]=i;
    }

    for (i=1;i<=n;i++)
     g<<final[i]<<'\n';
    return 0;
}