Cod sursa(job #253288)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 17:06:14
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
 using namespace std;  
   
 #include <bitset>  
 #define FOR(i,a,b) for(int i=a;i<=b;++i)  
 #define bit(x) ((x)&(x-1))^(x)  
   
 int N,poz;  
 int A[1<<15];  
   
 void update(int x)  
 {  
     for(int i=x;i<=N;i += bit(i) )  
         ++A[i];  
 }     
   
 int querry(int x,int y)  
 {    
     int sum(0);  
     for(int i=y;i>=1;i -= bit(i) )  
         sum += A[i];  
     for(int i=x-1;i>=1;i -= bit(i) )  
         sum -= A[i];  
     return y-x+1-sum;  
 }  
   
 int find(int K)  
 {  
     int m,step(1<<15);  
     int up = querry(poz+1,N);  
     int down = querry(1,poz);  
       
     if(K <= up)  
     {  
         for(m=poz+1;step;step >>= 1)  
             if(m+step <= N && querry(poz+1,m+step-1) < K)  
                 m += step;  
         return m;  
     }     
     if(K <= up + down)  
     {     
         for(m=1;step;step >>= 1)  
             if(m+step <= poz && querry(1,m+step-1) + up < K)  
                 m += step;  
         return m;  
     }  
     if(K % (up+down))  
         return find(K % (up+down));  
     return find(up+down);  
 }  
   
 int main()  
 {  
     freopen("order.in","r",stdin);  
     freopen("order.out","w",stdout);  
     scanf("%d",&N);  
       
     poz = 1;  
     FOR(i,1,N)  
     {  
         poz = find(i);  
         update(poz);  
         printf("%d ",poz);  
     }     
       
     return 0;  
}