Cod sursa(job #3250523)

Utilizator Dragu_AndiDragu Andrei Dragu_Andi Data 21 octombrie 2024 16:58:03
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int nmax=1e5 +1;
int aint[nmax*4], v[nmax], rasp[nmax];

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

void query(int i, int sum, int nod, int st, int dr)
{
    if(st==dr)
    {
        rasp[st]=i;
        aint[nod]=0;
        return;
    }
    if(sum<=aint[nod*2])
        query(i, sum, nod*2, st, (st+dr)/2);
    else
        query(i, sum-aint[nod*2], nod*2+1, (st+dr)/2+1, dr);
    aint[nod]=aint[nod*2]+aint[nod*2+1];
}

int main()
{
    int n;
    fin >> n;
    for(int i=1; i<=n; i++)
        fin >> v[i];
    build_aint(1, 1, n);
    for(int i=n; i>=1; i--)
    {
        query(i, v[i], 1, 1, n);
    }
    for(int i=1; i<=n; i++)
        fout << rasp[i] << '\n';
    return 0;
}