Cod sursa(job #3249027)

Utilizator mihai_moldovan11555mihai moldovan mihai_moldovan11555 Data 14 octombrie 2024 15:44:10
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int V[30005], Fen[30005], Rez[30005], n;

void Update(int poz, int val)
{
    for (int i = poz; i <= n; i += i & -i)
        Fen[i] += val;
}

int Query(int poz)
{
    int sum = 0;
    for (int i = poz; i; i -= i & -i)
        sum += Fen[i];

    return sum;
}

int CB(int val)
{
    int st = 1, dr = n, poz = -1;

    while (st <= dr)
    {
        int m = (st + dr) / 2;
        if (Query(m) >= val)
            poz = m, dr = m - 1;
        else
            st = m + 1;
    }

    return poz;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i ++)
        fin >> V[i];

    for (int i = 1; i <= n; i ++)
        Update(i, 1);

    for (int i = n; i >= 1; i --)
    {
        int poz = CB(V[i]);
        Rez[poz] = i;
        Update(poz, -1);
    }

    for (int i = 1; i <= n; i ++)
        fout << Rez[i] << '\n';
}