Cod sursa(job #3296018)

Utilizator cristia_razvanCristia Razvan cristia_razvan Data 10 mai 2025 19:05:26
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>

using namespace std;

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

int n;
int a[30005], aib[30005], ans[30005];

void update(int p, int x) {
    for (int i = p; i <= n; i += (i & -i)) {
        aib[i] += x;
    }
}

int query(int p) {
    int ans = 0;
    for (int i = p; i > 0; i -= (i & (-i))) ans += aib[i];

    return ans;
}

/// cea mai din stange pozitie poz cu sum a[1]+...a[poz]
int cb(int p, int s) {
    int st, dr, poz, mij;
    st = 1;
    dr = p;
    poz = 0;
    while (st <= dr) {
        int mid = (st + dr) >> 1;
        int sac = query(mid);
        if (sac == s) {
            poz = mid;
            dr = mid - 1;
        } else if (sac > s)
            dr = mid - 1;
        else
            st = mid + 1;
    }
    return poz;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
        update(i, 1);
    }
    for (int i = n; i >= 1; i--) {
        int p = cb(n, a[i]);
        update(p, -1);
        ans[p] = i;
    }

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

    return 0;
}