Cod sursa(job #2941527)

Utilizator Matei_MunteanuMunteanu Matei Ioan Matei_Munteanu Data 17 noiembrie 2022 20:44:32
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;

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

int n;
int N[30004];
int sol[30004];

struct BinaryIndexedTree
{
    vector<int> bit;
    void init()
    {
        bit.assign(n + 4, 0);
    }

    void add(int idx, int val)
    {
        while (idx <= n)
        {
            bit[idx] += val;
            idx += (idx & (-idx));
        }
    }

    int sum(int idx)
    {
        int total = 0;
        while (idx > 0)
        {
            total += bit[idx];
            idx -= (idx & (-idx));
        }
        return total;
    }

    int range_sum(int left, int right)
    {
        return sum(right) - sum(left - 1);
    }
} BIT;

int main()
{
    fin >> n;
    BIT.init();
    for (int i = 1; i <= n; i++)
    {
        fin >> N[i];
        BIT.add(i, 1);
    }
    for (int i = n; i >= 1; i--)
    {
        int p = 1;
        int val = N[i];
        while (p < n)
        {
            p <<= 1;
        }
        int poz = 0;
        while (p)
        {
            if ((poz + p) <= n && BIT.bit[poz + p] < val)
            {
                val -= BIT.bit[poz + p];
                poz += p;
            }
            p >>= 1;
        }
        poz++;
        sol[poz] = i;
        BIT.add(poz, -1);
    }
    for (int i = 1; i <= n; i++)
    {
        fout << sol[i] << '\n';
    }
    return 0;
}