Cod sursa(job #3210981)

Utilizator PetraPetra Hedesiu Petra Data 7 martie 2024 20:37:37
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>

#define NMAX 100003

using namespace std;

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

int n, v[NMAX], sol[NMAX], tree[NMAX];

void update(int p, int val)
{
    for (int j = p; j <= n; j += (j&(-j)))
        tree[j] += val;
}

int query(int p)
{
    int sum = 0;
    for (int i = p; i > 0; i -= (i&(-i)))
        sum +=  tree[i];
    return sum;
}

int binary_srch(int p)
{
    int st = 1, dr = n, poz = n;
    while (st <= dr)
    {
        int mijl = (st + dr) / 2;
        if (query(mijl) >= p)
        {
            dr = mijl - 1;
            poz = mijl;
        }
        else st = mijl + 1;
    }
    return poz;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> v[i];
        update(i, 1);
    }
    for (int i = n; i >= 1; i--)
    {
        int p = binary_srch(v[i]);
        update(p, -1);
        sol[p] = i;
    }
    for (int i = 1; i <= n; i++)
        fout << sol[i] << "\n";

    return 0;
}