Cod sursa(job #3244997)

Utilizator antonio_sefu_tauLaslau Antonio antonio_sefu_tau Data 26 septembrie 2024 22:30:16
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>
using namespace std;
const int dim=3e4+5;
int n,a[dim],aib[dim],sol[dim];
int lsb(int x){return x&(-x);}
void update(int poz, int val){
    for(int i=poz;i<=n;i+=lsb(i)){
        aib[i]+=val;
    }
}
int main(){
    ifstream f("schi.in");
    ofstream g("schi.out");
    f>>n;
    for(int i=1;i<=n;i++){
        f>>a[i];
        update(i,1);
    }
    for(int i=n;i>=1;i--){
        int poz=0,s=0;
        for(int k=16;k>=0;k--){
            if(poz+(1<<k)<=n and s+aib[poz+(1<<k)]<a[i]){
                s+=aib[poz+(1<<k)];
                poz+=(1<<k);
            }
        }
        if(poz<n){
            sol[poz+1]=i;
            update(poz+1,-1);
        }
    }
    for(int i=1;i<=n;i++){
        g<<sol[i]<<'\n';
    }
    return 0;
}