Cod sursa(job #2944145)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 22 noiembrie 2022 08:53:35
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int v[30000];
class fenwick{
    int fen[30000];
public:
    void add(int pos,int nr){
        pos++;
        for(int i = pos;i <= 30000;i+=i&-i){
            fen[i]+=nr;
        }
    }
    int get(int pos){
        pos++;
        int r = 0;
        for(int i = pos;i > 0;i-=i&-i){
            r+=fen[i];
        }
        return r;
    }
    int bs(int nr){
        ///returns the first number >= nr
        int sum = 0,pos = 0;
        for(int i = (1<<15);i > 0;i>>=1){
            if(pos + i <= 30000 && sum + fen[pos + i] < nr){
                sum+=fen[pos + i];
                pos+=i;
            }
        }
        return pos;
    }
};
fenwick f;
int ans[30000];
int main(){
    int n,i,pos,j;
    fin>>n;
    for(i = 0;i < n;i++)fin>>v[i];
    for(i = 0;i < n;i++)f.add(i,1);
    for(i = n - 1;i >= 0;i--){
        /*for(j = 0;j < n;j++){
            cout<<f.get(j)<<' ';
        }
        cout<<'\n';*/
        pos = f.bs(v[i]);
        ans[pos] = i + 1;
        f.add(pos,-1);
        //cout<<pos<<' '<<v[i]<<'\n';
    }
    for(i = 0;i < n;i++){
        fout<<ans[i]<<'\n';
    }
    return 0;
}