Pagini recente » Cod sursa (job #1246827) | Cod sursa (job #2398693) | Cod sursa (job #3172947) | Cod sursa (job #713230) | Cod sursa (job #2400504)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
const int N=300009;
int n,STEP;
int aint[2*N];
void build()
{
for(int i=1;i<=n;++i)
aint[i+n-1]=1;
for(int i=n-1;i>=1;--i)
aint[i]=aint[i<<1]+aint[(i<<1)|1];
}
void update(int a,int b)
{
for(aint[a+=n-1]=b;a>=1;a>>=1)
aint[a>>1]=aint[a]+aint[a^1];
}
int query(int st,int dr)
{
int ans=0;
for(st+=n-1,dr+=n;st<dr;st>>=1,dr>>=1)
{
if(st&1)
ans+=aint[st++];
if(dr&1)
ans+=aint[--dr];
}
return ans;
}
int binary(int val)
{
int ans=0,step=STEP;
for(;step;step>>=1)
{
if(query(1,ans+step)<val)
ans+=step;
}
return ans+1;
}
int main()
{
fin.sync_with_stdio(false);
fin>>n;
int nn=n,pas=0,curr=1;
STEP=1<<(int(log2(n)+1));
build();
while(nn)
{
pas++;
int next=(query(1,curr)+pas)%nn;
if(!next)
next+=nn;
int ans=binary(next);
update(ans,0);
fout<<ans<<" ";
curr=ans;
nn--;
}
return 0;
}