Cod sursa(job #3367615)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 8 octombrie 2026 21:52:52
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>

using namespace std;

int v[30005], aint[120005];
int sol[30005];

void build(int l, int r, int x)
{
    if (l == r)
    {
        aint[x] = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * x);
    build(mid + 1, r, 2 * x + 1);
    aint[x] = aint[2 * x] + aint[2 * x + 1];
}

void update(int l, int r, int x, int poz, int val)
{
    if (l == r)
    {
        aint[x] -= val;
        return;
    }
    int mid = (l + r) / 2;
    if (poz <= mid)
    {
        update(l, mid, 2 * x, poz, val);
    }
    else
    {
        update(mid + 1, r, 2 * x + 1, poz, val);
    }
    aint[x] = aint[2 * x] + aint[2 * x + 1];
}

int query(int l, int r, int x, int liml, int limr)
{
    if (l > limr || r < liml)
    {
        return 0;
    }
    if (liml <= l && limr >= r)
    {
        return aint[x];
    }
    int mid = (l + r) / 2;
    return query(l, mid, 2 * x, liml, limr) + query(mid + 1, r, 2 * x + 1, liml, limr);
}

int walk(int l, int r, int x, int sum) {
    if(l == r) {
        return l;
    }
    int mid = (l + r) / 2;
    if(aint[2 * x] >= sum) {
        return walk(l, mid, 2 * x, sum);
    } else {
        return walk(mid + 1, r, 2 * x + 1, sum - aint[2 * x]);
    }
}

int main() 
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
	int n, m; cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> v[i];
    }
    build(1, n, 1);
    for(int i = n; i >= 1; i--) {
        //int st = 1;
        //int dr = n;
        int pos = walk(1, n, 1, v[i]);
        // while(st <= dr) {
        //     int mid = (st + dr) / 2;
        //     if(query(1, n, 1, 1, mid) > v[i]) {
        //         dr = mid - 1;
        //     } else {
        //         if(query(1, n, 1, 1, mid) < v[i]) {
        //             st = mid + 1;
        //         } else {
        //             pos = mid;
        //             dr = mid - 1;
        //         }
        //     }
        // }
        sol[pos] = i;
        update(1, n, 1, pos, 1);
    }
    for(int i = 1; i <= n; i++) {
        cout << sol[i] << '\n';
    }
    
}