Cod sursa(job #3204744)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 17 februarie 2024 13:04:18
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
// sunt bun si la schi irl . 90.2 km/h slabilor (take the L)

#include <fstream>
using namespace std;

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

int rasp1[30001],aib[30002],v[30001],n;

void update(int poz,int nr){
    while(poz<=n){//printf("(%d)",nr);
        aib[poz]+=nr;
        poz+=(poz&(-poz));
    }
}

int query(int poz){
    int rasp=0;
    while(poz>0){
        rasp+=aib[poz];
        poz-=(poz&(-poz));
    }
    return rasp;
}

int main()
{
    int i,st,dr,rasp,mij;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>v[i];
        update(i,1);
    }
    for(i=n;i>0;i--){
        st=1;dr=rasp=n;
        while(st<=dr){
            mij=(st+dr)/2;
            if(query(mij)>=v[i]){
                dr=mij-1;rasp=mij;
            }else{
                st=mij+1;
            }
        }
        rasp1[rasp]=i;
        update(rasp,-1);
    }
    for(i=1;i<=n;i++) cout<<rasp1[i]<<"\n";
    return 0;
}