Cod sursa(job #1184087)

Utilizator apopeid15Apopei Daniel apopeid15 Data 11 mai 2014 11:19:23
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>
 
int a[30001],n;
 
void update(int x,int val){
    while ( x<=n ){
        a[x]+=val;
        x+=(x&(-x));
    }
}
 
int query(int x){
    if ( x==0 )
        return 0;
    return a[x]+query(x-(x&(-x)));
}
 
int main(){
    FILE*f=fopen("order.in","r");
    FILE*h=fopen("order.out","w");
    fscanf(f,"%d",&n);
    for ( int i=1;i<=n;++i )
        update(i,1);
    int cerc=n,poz=2;
    for ( int i=1;i<=n;++i ){
        --cerc;
        int p=0;
        for ( int pas=1<<14;pas;pas=pas>>1 )
            if ( p+pas<=n&&query(p+pas)<poz )
                p+=pas;
        ++p;
        update(p,-1);
        fprintf(h,"%d ",p);
        poz+=i;
        if ( cerc )poz%=cerc;
        if ( !poz )poz=cerc;
    }
    return 0;
}