Cod sursa(job #3248298)

Utilizator amavutsiviataAndrei Preda amavutsiviata Data 11 octombrie 2024 15:04:04
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>

using namespace std;

int aib[30005], n, i, x, v[30005], viz[30005];

void update(int ind)
{
    while (ind <= n)
    {
        aib[ind]++;
        ind += ind & -ind;
    }
}

int query(int ind)
{
    int rez = 0;
    while (ind)
    {
        rez+=aib[ind];
        ind -= ind&-ind;
    }
    return rez;
}

int main()
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    for (i = n; i > 0; i--)
    {
        int st = 1, dr = n, pos = 0;
        while (st <= dr)
        {
            int mij = (st + dr)/2;
            if (mij - query(mij) >= v[i])
            {
                pos = mij;
                dr = mij - 1;
            }
            else st = mij + 1;
        }
        update(pos);
        viz[pos] = i;
    }
    for (i = 1; i <= n; i++) cout << viz[i] << '\n';
    return 0;
}