Cod sursa(job #1410099)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 30 martie 2015 21:00:24
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<cstdio>
const int N=30000;
int aib[N+1];
int n,lol;
bool f;
void update(int pos,int val){
    while(pos<=n){
        aib[pos]+=val;
        pos+=pos&(-pos);
    }
}
int query(int pos){
    int r=0;
    while(pos>0){
        r+=aib[pos];
        pos-=pos&(-pos);
    }
    return r;
}
int bsearch(int val){
    int p=1<<15;
    int pos=0;
    int sum=0;
    while(p){
        if(p+pos<=n)
            if(sum+aib[pos+p]<val){
                pos+=p;
                sum+=aib[pos];
            }
        p/=2;
    }
    return pos+1;
}
int main(){
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    int pos=1;
    for(int i=1;i<=n;i++)
        update(i,1);
    for(int i=1;i<=n;i++){
        lol=i-1;
        int pas=i;
        pas+=query(pos);
        pas%=(n-i+1);
        if(pas==0)
            pas=n-i+1;
        pos=bsearch(pas);
        update(pos,-1);
        printf("%d ",pos);
    }
    return 0;
}