Cod sursa(job #2944146)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 22 noiembrie 2022 08:57:41
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
std::ifstream fin("schi.in");
std::ofstream fout("schi.out");
typedef unsigned short int si;
si v[30000];
class fenwick{
    si fen[30000];
public:
    void add(si pos,short int nr){
        pos++;
        for(si i = pos;i <= 30000;i+=i&-i){
            fen[i]+=nr;
        }
    }
    si bs(si nr){
        ///returns the first number >= nr
        si sum = 0,pos = 0;
        for(si i = (1<<14);i > 0;i>>=1){
            if(pos + i <= 30000 && sum + fen[pos + i] < nr){
                sum+=fen[pos + i];
                pos+=i;
            }
        }
        return pos;
    }
};
fenwick f;
si ans[30000];
int main(){
    si 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 != 65535;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);
        //fout<<pos<<' '<<v[i]<<'\n';
    }
    for(i = 0;i < n;i++){
        fout<<ans[i]<<'\n';
    }
    return 0;
}