Cod sursa(job #3338860)

Utilizator ilie_2008Iamboglo Ilie ilie_2008 Data 5 februarie 2026 12:07:17
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
using namespace std;

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

int N;
int poz[30001];
int BIT[30001];
int sol[30001];

int main() {
    fin >> N;

    for (int i = 1; i <= N; i++)
        fin >> poz[i];

    for (int i = 1; i <= N; i++) {
        int j = i;
        while (j <= N) {
            BIT[j] += 1;
            j += j & (-j);
        }
    }

    for (int i = N; i >= 1; i--) {
        int k = poz[i];
        int st = 1, dr = N, ans = N;

        while (st <= dr) {
            int mid = (st + dr) / 2;
            int s = 0, x = mid;
            while (x > 0) {
                s += BIT[x];
                x -= x & (-x);
            }

            if (s >= k) {
                ans = mid;
                dr = mid - 1;
            } else {
                st = mid + 1;
            }
        }

        sol[ans] = i;

        int x = ans;
        while (x <= N) {
            BIT[x]--;
            x += x & (-x);
        }
    }

    for (int i = 1; i <= N; i++)
        fout << sol[i] << "\n";

    return 0;
}