Cod sursa(job #3247269)

Utilizator CaldareaCiprianCaldarea Ciprian CaldareaCiprian Data 6 octombrie 2024 17:55:31
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

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

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

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

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

    return nr;

}


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

    VI poz(n + 1);
    int ma;
    for (ma = 1; ma <= n; ma <<= 1);
    ma >>= 1;
    for (int i = n; i >= 1; --i)
    {
        int good, cur = 0;
        int bit = ma;
        while (bit != 0)
        {
            cur += bit;
            if (Query(cur) >= v[i])
            {
                good = cur;
                cur -= bit;
            }

            bit >>= 1;

        }

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

    }

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



}