Cod sursa(job #3304135)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 21 iulie 2025 09:34:13
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>

using namespace std;

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

const int nmax = 30000;
int n, a[nmax + 2], place[nmax + 2];

inline int f(int x){ return (x & (-x)); }
struct fenwicktree{
    int tree[nmax + 2], intotal;

    void add(int pos, int val){
        for(int i = pos; i <= n; i += f(i))
            tree[i] += val;
        intotal += val;
    }

    int sum(int pos){
        int s = 0;
        for(int i = pos; i >= 1; i -= f(i))
            s += tree[i];
        return s;
    }

    int getkth(int k){
        int pos = 0;
        for(int b = 14; b >= 0; b--){
            if((pos | (1 << b)) <= n && tree[pos | (1 << b)] < k)
                pos |= (1 << b), k -= tree[pos];
        }
        return pos + 1;
    }
} aib;

int main(){

    in.tie(NULL) -> sync_with_stdio(false);

    in>>n;
    for(int i = 1; i <= n; i++)
        in>>a[i];

    for(int i = 1; i <= n; i++){
        aib.tree[i]++;
        if(i + f(i) <= n)
            aib.tree[i + f(i)] += aib.tree[i];
    }

    for(int i = n; i >= 1; i--){
        int p = aib.getkth(a[i]);

        place[p] = i;
        aib.add(p, -1);
    }

    for(int i = 1; i <= n; i++)
        out<<place[i]<<"\n";

    return 0;
}