Cod sursa(job #3319760)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 3 noiembrie 2025 10:44:28
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <iostream>

using namespace std;
const int MAXN = 30000;
int rez[MAXN + 1], aib[MAXN + 1], v[MAXN + 1];
int n;
void addBit(int poz, int val) {
    while (poz <= n) {
        aib[poz] += val;
        poz += (poz & (-poz));
    }
}
int main()
{
    FILE *fin, *fout;
    int i, p, p2, poz, s;
    fin = fopen("schi.in", "r");
    fscanf(fin, "%d", &n);
    for (i = 1; i <= n; i++) {
        fscanf(fin, "%d", &v[i]);
        addBit(i, 1);
    }
    fclose(fin);
    p2 = 1;
    while ((1 << p2) <= n) {
        p2++;
    }
    p2--;
    //fiecare intra pe a v[i]-a pozitie libera
    for (i = n; i > 0; i--) {
        //caut suma = v[i]
        poz = s = 0;
        for (p = p2; p >= 0; p--) {
            if (poz + (1 << p) <= n && s + aib[poz + (1 << p)] < v[i]) {
                s += aib[poz + (1 << p)];
                poz += (1 << p);
            }
        }
        poz++;
        rez[poz] = i;
        addBit(poz, -1);
    }
    fout = fopen("schi.out", "w");
    for (i = 1; i <= n; i++) {
        fprintf(fout, "%d\n", rez[i]);
    }
    fclose(fout);
    return 0;
}