Cod sursa(job #3362974)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 13 august 2026 11:46:35
Problema Schi Scor 100
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>

#define MAXN 32768

int v[MAXN + 1], f[MAXN + 1], poz[MAXN + 1], arb[2 * MAXN];

int query(int n, int sum) {
    int st, dr, nod, p2;

    nod = p2 = st = 1;
    dr = n;
    while (p2 <= n) {
        if (arb[2 * nod] >= sum) {
            dr = (st + dr) / 2;
            nod = 2 * nod;
        } else {
            st = (st + dr) / 2 + 1;
            sum -= arb[2 * nod];
            nod = 2 * nod + 1;
        }
        p2 *= 2;
    }

    return dr;
}

void update(int n, int idx, int val) {
    int poz;

    poz = n + idx - 1;
    arb[poz] = val;
    n /= 2;
    while (n) {
        poz = (poz - (poz & 1)) / 2;
        arb[poz] = arb[2 * poz] + arb[2 * poz + 1];
        n /= 2;
    }
}

int main() {
    FILE *fin, *fout;
    int n, np2, p2, rez, i;

    fin = fopen("schi.in", "r");
    fscanf(fin, "%d", &n);
    for (i = 1; i <= n; i++) {
        fscanf(fin, "%d", &v[i]);
        f[i] = 1;
    }
    fclose(fin);

    p2 = 1;
    while (p2 < n) {
        p2 *= 2;
    }
    np2 = p2;

    for (i = np2; i < 2 * np2; i++) {
        arb[i] = f[i - np2 + 1];
    }
    p2 /= 2;
    while (p2) {
        for (i = p2; i < 2 * p2; i++) {
            arb[i] = arb[2 * i] + arb[2 * i + 1];
        }
        p2 /= 2;
    }

    for (i = n; i >= 1; i--) {
        rez = query(np2, v[i]);
        printf("%d %d %d\n", i, v[i], rez);
        poz[rez] = i;
        update(np2, rez, 0);
    }

    fout = fopen("schi.out", "w");
    for (i = 1; i <= n; i++) {
        fprintf(fout, "%d\n", poz[i]);
    }
    fclose(fout);

    return 0;
}