Cod sursa(job #2922493)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 8 septembrie 2022 17:35:54
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <stack>

using namespace std;

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

#define zeros(x)(x & (-x))

const int max_size = 3e4 + 1;

int aib[max_size], a[max_size], ans[max_size], n;

void update (int poz, int val)
{
    for (int i = poz; i <= n; i += zeros(i))
    {
        aib[i] += val;
    }
}

int querry (int poz)
{
    int rez = 0;
    for (int i = poz; i > 0; i -= zeros(i))
    {
        rez += aib[i];
    }
    return rez;
}

int main ()
{
    int e = 1;
    in >> n;
    while (e <= n)
    {
        e *= 2;
    }
    e /= 2;
    for (int i = 1; i <= n; i++)
    {
        in >> a[i];
        update(i, 1);
    }
    for (int i = n; i > 0; i--)
    {
        int val = a[i];
        int st = n, ec = e;
        while (ec >>= 1)
        {
            if (querry(st - ec) >= val)
            {
                st -= ec;
            }
        }
        while (querry(st) < val)
        {
            st++;
        }
        ans[st] = i;
        update(st, -1);
    }
    for (int i = 1; i <= n; i++)
    {
        out << ans[i] << '\n';
    }
    in.close();
    out.close();
    return 0;
}