Cod sursa(job #3247460)

Utilizator vladneaguvladCristianoRonaldo vladneagu Data 7 octombrie 2024 20:33:14
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <iostream>
using namespace std;
int v[100000],bit[100000],rasp[100000];
int n;
void update(int poz,int val){
    while(poz<=n){
        bit[poz]+=val;
        poz=poz+(poz&-poz);
    }
}
int query(int poz){
    int rasp=0;
    while(poz>0){
        rasp+=bit[poz];
        poz-=(poz&(-poz));
    }
    return rasp;
}
int main()
{
    cin>>n;
    for (int i = 1; i <=n; i++) {
        cin>>v[i];
        update(i,1);
    }
    for(int i=n;i>0;i--){
        int st=1,dr=n,rsp=n;
        while(st<=dr){
            int mij=(st+dr)/2;
            if(query(mij)>=v[i]){
                dr=mij-1;
                rsp=mij;
            }else{
                st=mij+1;
            }
        }
        rasp[rsp]=i;
        update(rsp,-1);
    }
    for(int i=1;i<=n;i++) cout<<rasp[i]<<"\n";
    return 0;
}