Cod sursa(job #3247279)

Utilizator CaldareaCiprianCaldarea Ciprian CaldareaCiprian Data 6 octombrie 2024 18:50:06
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

using ll = int;
using VI = vector<ll>;
VI v, aib;
ll n;

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

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

ll Query(ll poz)
{
    ll nr = 0;
    for (ll i = poz; i > 0; i -= (i & -i))
        nr += aib[i];

    return nr;

}


int main()
{
    fin >> n;
    v = aib = VI(n + 2);
    for (ll i = 1; i <= n; ++i)
    {
        fin >> v[i];
        Update(i, 1);
    }

    VI poz(n + 3);
    ll ma;
    ll good = 0, cur = 0;
    ll bit;
    for (ma = 1; ma <= n; ma <<= 1);
    ma >>= 1;

    for (ll i = n; i >= 1; --i)
    {
        cur = 0;
        good = 0;
        bit = ma;
        while (bit > 0)
        {
            cur += bit;

            if (cur > n)
            {
                cur -= bit;
                bit >>= 1;
                continue;
            }

            if (Query(cur) >= v[i])
            {
                good = cur;
                cur -= bit;
            }


            bit >>= 1;

        }

        poz[good] = i;
        Update(good, -1);

    }

    for (ll i = 1; i <= n; ++i)
        fout << poz[i] << '\n';

    fin.close();
    fout.close();

    return 0;

}