Cod sursa(job #1410070)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 30 martie 2015 20:41:47
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<cstdio>
void lel(){
    int x=0;
    x++;
}
const int N=30000;
int aib[N+1];
int n,lol;
bool f;
void update(int pos,int val){
    pos=n-pos+1;
    while(pos<=n){
        aib[pos]+=val;
        pos+=pos&(-pos);
    }
}
int query(int pos){
    pos=n-pos+1;
    int r=0;
    while(pos>0){
        r+=aib[pos];
        pos-=pos&(-pos);
    }
    if(!f)
        r--;
    f=true;
    return n-lol-r;
}
int bsearch(int val){
    int p=1<<15;
    int pos=0;
    int sum=0;
    val=n-lol-val+1;
    while(p){
        if(p+pos<=n)
            if(sum+aib[pos+p]<=val&&aib[pos+p]!=0&&sum+aib[pos+p/2]!=val){
                pos+=p;
                sum+=aib[pos];
            }
        p/=2;
    }
    return n-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++){
        if(i==5)
            lel();
        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;
}