Cod sursa(job #212522)
Utilizator | Data | 5 octombrie 2008 19:34:40 | |
---|---|---|---|
Problema | Order | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.22 kb |
# include <cstdio>
using namespace std;
# define FIN "order.in"
# define FOUT "order.out"
# define MAXN 30000
int N,i,j,poz,a,b,c,l1,l2;
int A[3*MAXN];
void build(int nod,int st,int dr)
{
int mij;
if (st == dr)
A[nod] = 1;
else
{
mij = (st + dr) >> 1;
build(nod<<1,st,mij);
build(nod<<1|1,mij+1,dr);
A[nod] = A[nod<<1] + A[nod<<1|1];
}
}
void query(int nod,int st,int dr)
{
int mij;
if (a <= st && dr <= b)
c += A[nod];
else
{
mij = (st + dr) >> 1;
if (a <= mij)
query(nod<<1,st,mij);
if (b > mij)
query(nod<<1|1,mij+1,dr);
}
}
void update(int nod,int st,int dr)
{
int mij;
if (st == dr)
{
printf("%d ",st);
poz = st;
A[nod] = 0;
}
else
{
mij = (st + dr) >> 1;
if (c <= A[nod<<1])
update(nod<<1,st,mij);
else
{
c -= A[nod<<1];
update(nod<<1|1,mij+1,dr);
}
A[nod] = A[nod<<1] + A[nod<<1|1];
}
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d",&N);
build(1,1,N);
poz = 1;
for (i = 1; i <= N; ++i)
{
c = 0; a = poz+1; b = N;
query(1,1,N);
l1 = c;
c = 0; a = 1; b = poz;
query(1,1,N);
l2 = c;
c = i;
if (c > l1+l2)
if (c % (l1+l2)) c -= i/(l1+l2)*(l1+l2);
else c = l1+l2;
if (c <= l1)
{
c += l2;
update(1,1,N);
}
else
{
c -= l1;
update(1,1,N);
}
}
return 0;
}