Cod sursa(job #3338895)

Utilizator moticailovitalieMoticailo Vitalie moticailovitalie Data 5 februarie 2026 13:12:47
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
using namespace std;

const int MAXN = 30005;

int N;
int arbore[MAXN];
int rezultat[MAXN];
int pozitii[MAXN];

void adauga(int poz, int valoare) {
    for (int i = poz; i <= N; i += i & -i)
        arbore[i] += valoare;
}

int sumaPrefix(int poz) {
    int s = 0;
    for (int i = poz; i > 0; i -= i & -i)
        s += arbore[i];
    return s;
}

int cautaPozitie(int k) {
    int stanga = 1, dreapta = N, mijloc, pozitie = -1;

    while (stanga <= dreapta) {
        mijloc = (stanga + dreapta) / 2;

        if (sumaPrefix(mijloc) >= k) {
            pozitie = mijloc;
            dreapta = mijloc - 1;
        } else {
            stanga = mijloc + 1;
        }
    }

    return pozitie;
}

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

    fin >> N;

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

    for (int i = 1; i <= N; i++)
        adauga(i, 1);

    for (int i = N; i >= 1; i--) {
		int loc = pozitii[i];
		int pozitieLibera = cautaPozitie(loc);
		rezultat[pozitieLibera] = i;
		adauga(pozitieLibera, -1);
    }

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

    return 0;
}