Pagini recente » Cod sursa (job #1454428) | Cod sursa (job #2281000) | Cod sursa (job #2567936) | Cod sursa (job #2139956) | Cod sursa (job #957381)
Cod sursa(job #957381)
#include <cstdio>
using namespace std;
inline int max(int a,int b)
{
if(a>b)
return a;
return b;
}
inline int tata(const int nod)
{
return nod/2;
}
inline int fiu1(const int nod)
{
return nod<<1;
}
inline int fiu2(const int nod)
{
return (nod<<1)+1;
}
struct sp
{
int a=0,b=0;
int val=0;
} v[500000];
void build(const int nod,const int a,const int b)
{
v[nod].a=a;
v[nod].b=b;
v[nod].val=0;
if(a<b)
{
int mij=(a+b)>>1;
build(fiu1(nod),a,mij);
build(fiu2(nod),mij+1,b);
}
}
int x;
void get_x(int n)
{
while(n)
{
x++;
n=n>>1;
}
}
inline void update(int nod)
{
while(tata(nod)!=nod)
{
v[nod].val=v[fiu1(nod)].val+v[fiu2(nod)].val;
nod=tata(nod);
}
}
int poz=2;
int sol;
void query(const int nod,int val)
{
if(nod>((1<<(x-1))-1))
{
sol=nod;
return;
}
if(val>v[fiu1(nod)].val)
{
query(fiu2(nod),val-v[fiu1(nod)].val);
}
else
query(fiu1(nod),val);
}
int n;
int main()
{
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
scanf("%d",&n);
int np=n;
while((n&(n-1))!=0)
n++;
get_x(n);
build(1,1,n);
for(int i=1;i<=np;i++)
{
v[(1<<(x-1))+i-1].val=1;
}
for(int i=(1<<(x-1))-1;i>=1;i--)
{
v[i].val=v[fiu1(i)].val+v[fiu2(i)].val;
}
/*for(int i=1,poz=1;i<=n;i=i*2)
{
for(int j=1;j<=i;j++,poz++)
{
printf("%d ",v[poz].val);
}
printf("\n");
}*/
for(int i=1;i<=np;i++)
{
poz+=i-1;
poz=poz%v[1].val;
if(poz==0)
poz=v[1].val;
sol=0;
query(1,poz);
v[sol].val=0;
update(tata(sol));
printf("%d ",sol-(1<<(x-1))+1);
}
return 0;
}