Pagini recente » Istoria paginii runda/muzica | Cod sursa (job #2945839) | Cod sursa (job #2460448) | Cod sursa (job #1223507) | Cod sursa (job #236308)
Cod sursa(job #236308)
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;
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(1<<15);
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) + up < K)
m += step;
return m;
}
if(K % (up+down))
return find(K % (up+down));
return find(up+down);
}
int main()
{
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
scanf("%d",&N);
poz = 1;
FOR(i,1,N)
{
poz = find(i);
update(poz);
printf("%d ",poz);
}
return 0;
}