Cod sursa(job #3134349)

Utilizator AlexTrandafir09Trandafir Alexandru Ionut AlexTrandafir09 Data 28 mai 2023 22:05:06
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("../schi.in");
ofstream g("../schi.out");
int n;
int arbore[120000], v[30000], rezultat[30000];

void construieste(int i_nod, int i_min, int i_max) {
    if (i_min == i_max) {
        arbore[i_nod] = 1;
        return;
    }
    int mij = (i_min + i_max) / 2;
    construieste(i_nod * 2, i_min, mij);
    construieste(i_nod * 2 + 1, mij + 1, i_max);
    arbore[i_nod] = arbore[i_nod * 2] + arbore[i_nod * 2 + 1];
}

int cauta(int i_nod, int i_min, int i_max, int p) {
    if (i_min == i_max) {
        arbore[i_nod] = 0;
        return i_min;
    }
    int mij = (i_min + i_max) / 2;
    int x;
    if (p <= arbore[i_nod * 2]) {
        x = cauta(i_nod * 2, i_min, mij, p);
    } else {
        x = cauta(i_nod * 2 + 1, mij + 1, i_max, p - arbore[i_nod * 2]);
    }
    arbore[i_nod] = arbore[i_nod * 2] + arbore[i_nod * 2 + 1];
    return x;
}

int main() {

    f>>n;

    for (int i = 1; i <= n; i++) {
        f>>v[i];
    }

    construieste(1, 1, n);

    for (int i = n; i >= 1; i--) {
        rezultat[cauta(1, 1, n, v[i])] = i;
    }

    for (int i = 1; i <= n; i++) {
        g<<rezultat[i]<<endl;
    }

    return 0;
}