Cod sursa(job #3133134)

Utilizator daria_lapadusLapadus Daria daria_lapadus Data 25 mai 2023 10:31:28
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
#define lsb(p) ((-p)&p)

using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");

int arb[30010], clasamentIntermediar[30010], clasamentFinal[30010], n;

void actualizare(int valoare, int pozitie) {
    for (int i = pozitie; i <= n; i += lsb(i)) {
        arb[i] += valoare;
    }
}

int suma(int pozitie) {
    int sum = 0;
    for (int i = pozitie; i > 0; i -= lsb(i)) {
        sum += arb[i];
    }
    return sum;
}

int cautareBinara(int x) {
    int stanga = 1, dreapta = n, mijloc, val;
    while (stanga <= dreapta) {
        mijloc = (stanga + dreapta) / 2;
        int aux = suma(mijloc);
        if (aux == x) {
            dreapta = mijloc - 1;
            val = mijloc;
        } else if (aux < x) {
            stanga = mijloc + 1;
        } else {
            dreapta = mijloc - 1;
        }
    }
    return val;
}

int main() {

    f >> n;
    for (int i = 1; i <= n; ++i) {
        f >> clasamentIntermediar[i];
        actualizare(1, i);
    }
    for (int i = n; i >= 1; --i) {
        int aux = cautareBinara(clasamentIntermediar[i]);
        clasamentFinal[aux] = i;
        actualizare(-1, aux);
    }
    for (int i = 1; i <= n; ++i) {
        g << clasamentFinal[i] << "\n";
    }

    f.close();
    g.close();

    return 0;
}