Cod sursa(job #2108270)

Utilizator calin9819Costea Calin calin9819 Data 18 ianuarie 2018 01:32:08
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int arbore[100000], sir[30001], rasp[30001];

void arb(int r, int st, int dr)
{
    if(st == dr)
    {
        arbore[r] = 1;
        return;
    }
    int mijloc = (st + dr)/2;
    arb(r * 2, st, mijloc);
    arb(r * 2 + 1, mijloc + 1, dr);
    arbore[r] = arbore[2 * r] + arbore[2 * r + 1];
}

int update(int st, int dr, int r, int nr_poz)
{
    arbore[r]--;
    int mijloc = (st + dr)/2;
    if(st == dr) return st;
    if(nr_poz <= arbore[2 * r]) return update(st, mijloc, 2 * r, nr_poz);
    return update(mijloc + 1, dr, 2 * r + 1, nr_poz - arbore[2 * r]);
}

int main()
{
    int N;
    f >> N;
    for (int i = 1; i <= N; i++)
        f >> sir[i];
    arb(1, 1, N);

    for(int i = N; i > 0; i--)
        rasp[update(1, N, 1, sir[i])] = i;
    for(int i = 1; i <= N; i++)
        g << rasp[i]<<'\n';
    return 0;
}