Pagini recente » Cod sursa (job #2040233) | Cod sursa (job #576040) | Cod sursa (job #1307660) | Cod sursa (job #1382170) | Cod sursa (job #2400513)
#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 st=1,dr=n;
int sol=-1;
while(st<=dr)
{
int mij=(st+dr)/2,ans=query(1,mij);
if(ans==val)
sol=mij;
if(ans>=val)
dr=mij-1;
else
st=mij+1;
}
return sol;
}
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;
}