Pagini recente » Cod sursa (job #2869613) | Cod sursa (job #1637678) | Cod sursa (job #2528768) | Cod sursa (job #2738284) | Cod sursa (job #236295)
Cod sursa(job #236295)
using namespace std;
#include <bitset>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define bit(x) ((x)&(x-1))^(x)
int N,poz,Step;
int A[1<<15];
void update(int x)
{
for(int i=x;i<=N;i += bit(i) )
++A[i];
}
int querry(int x,int y)
{
int sum(0);
for(int i=y;i>=1;i -= bit(i) )
sum += A[i];
for(int i=x-1;i>=1;i -= bit(i) )
sum -= A[i];
return y-x+1-sum;
}
int find(int K)
{
int m,step(Step);
int up = querry(poz+1,N);
int down = querry(1,poz);
if(K <= up)
{
for(m=poz+1;step;step >>= 1)
if(m+step <= N && querry(poz+1,m+step-1) < K)
m += step;
return m;
}
if(K <= up + down)
{
for(m=1;step;step >>= 1)
if(m+step <= poz && querry(1,m+step-1) + down < K)
m += step;
return m;
}
return find(K % (up+down) );
}
int main()
{
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
scanf("%d",&N);
poz = 1;
for(Step = 1;Step <= N;Step <<= 1);
FOR(i,1,N)
{
poz = find(i);
update(poz);
printf("%d ",poz);
}
return 0;
}