Nu aveti permisiuni pentru a descarca fisierul grader_test18.in
Cod sursa(job #143545)
Utilizator | Data | 26 februarie 2008 17:24:19 | |
---|---|---|---|
Problema | Order | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.25 kb |
#include<stdio.h>
long n,arb[(1<<17)];
void fa(long poz,long st,long dr)
{
arb[poz] = dr - st +1;
if( dr == st) return ;
fa(poz*2,st,(st+dr)/2);
fa(poz*2+1,(st+dr)/2+1,dr);
}
long afla( long poz, long st,long dr, long cat)
{
if( dr <= cat)
return arb[poz];
if( st > cat) return 0;
if( arb[poz] == 0) return 0;
return afla(poz*2,st,(st+dr)/2,cat) + afla(poz*2+1,(st+dr)/2+1,dr,cat);
}
long afla2( long poz,long st,long dr,long cine)
{
if( st == dr)
return st;
if( arb[poz*2] >= cine)
{
long x = afla2(poz*2,st,(st+dr)/2,cine);
return x;
}
long x = afla2(poz*2+1,(st+dr)/2+1,dr,cine-arb[poz*2]);
return x;
}
void elimina(long poz,long st,long dr,long cine)
{
if( cine < st || cine > dr)
return ;
arb[poz]--;
if( st == dr) return;
elimina(poz*2,st,(st+dr)/2,cine);
elimina(poz*2+1,(st+dr)/2+1,dr,cine);
}
int main()
{
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
scanf("%ld",&n);
fa(1,1,n);
long act = 1;
for( long i = 1; i <= n; ++i)
{
long ask = afla(1,1,n,act) + i;
ask %= (n-i+1);
if( ask == 0) ask = n-i+1;
act = afla2(1,1,n,ask);
if( i == n)
printf("%ld\n",act);
else printf("%ld ",act);
elimina(1,1,n,act);
}
return 0;
}