Cod sursa(job #3363401)

Utilizator Alexutu008Ionita Alexandru-Dumitru Alexutu008 Data 17 august 2026 15:42:58
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;

const int max_size = 3e4 + 1, max_heap = 12e4 + 1;

int n, x;
vector<int> v;
int aint[max_heap], placement[max_size]; // pozitiile libere

void init(int l, int r, int nod)
{
    if (l == r)
    {
        aint[nod] = 1;
        return;
    }
    int m = l + r >> 1;
    init(l, m, nod << 1);
    init(m + 1, r, (nod << 1) + 1);
    aint[nod] = aint[nod << 1] + aint[(nod << 1) + 1];
}

void update(int l, int r, int poz, int nod, int val)
{
    if (l == r)
    {
        aint[nod] = val;
        return;
    }
    int m = l + r >> 1;
    if (poz <= m)
        update(l, m, poz, nod << 1, val);
    else
        update(m + 1, r, poz, (nod << 1) + 1, val);
    aint[nod] = aint[nod << 1] + aint[(nod << 1) + 1];
}

int query(int l, int r, int val, int nod)
{
    if (l == r)
    {
        return l;
    }
    int m = l + r >> 1;
    if (val <= aint[2 * nod])
        return query(l, m, val, nod << 1);
    else
        return query(m + 1, r, val - aint[2 * nod], (nod << 1) + 1);
}

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> x;
        v.push_back(x);
    }
    init(1, n, 1);
    while (!v.empty())
    {
        int x = v.back();
        v.pop_back();
        int place = query(1, n, x, 1);
        placement[place] = v.size() + 1;
        update(1, n, place, 1, 0);
    }

    for (int i = 1; i <= n; ++i)
        cout << placement[i] << '\n';

    return 0;
}