Cod sursa(job #1663342)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 25 martie 2016 20:55:36
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<cstdio>
int n,i,j,a,b,nr,v[30100],x[30100];
FILE *f,*g;
void upd(int poz,int val){
    for(int i=poz;i<=n;i += ( i & ( - i ) ) ){
        v[i] += val;
    }
}
int verif(int poz){
    int s = 0;
    for(int i=poz;i>0;i -= ( i & ( -i ) ) ){
        s += v[i];
    }
    return s;
}
int query(int val){
    int s = 0;
    int p = 1;
    int i = 0;
    for(;p<=n;p*=2){}
    for(;p>0;p/=2){
        if( i + p <= n && s + v[ i + p ] < val ){
            s += v[ i + p ];
            i += p;
        }
    }
    if( i < n && verif( i + 1 ) == val )
        return i + 1;
    return -1;
}
int main(){
    f=fopen("order.in","r");
    g=fopen("order.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++){
        upd(i,1);
    }
    nr = 1;
    for(i=1;i<=n;i++){
        nr = ( nr + i ) % ( n - i + 1 );
        if( !nr )
            nr = n - i + 1;
        a = query(nr);
        upd(a,-1);
        fprintf(g,"%d ",a);
        nr--;
    }








    fclose(f);
    fclose(g);
    return 0;
}