Pagini recente » Cod sursa (job #1416402) | Cod sursa (job #840479) | Cod sursa (job #1965652) | Cod sursa (job #2461177) | Cod sursa (job #856309)
Cod sursa(job #856309)
#include <cstdio>
#define lsb(x) x&(-x)
int n,aib[30009];
void update(int poz)
{
for (;poz<=n;poz+=lsb(poz))
++aib[poz];
}
void del(int poz)
{
for (;poz<=n;poz+=lsb(poz))
--aib[poz];
}
int getnr(int poz)
{int nr=0;
for (;poz>0;poz-=lsb(poz))
nr+=aib[poz];
return nr;
}
int search(int poz)
{
int x=1,y=n,z,rez=n;
while (x<=y)
{
z=(x+y)/2;
int nr=getnr(z);
if (nr>=poz)
rez=z,y=z-1; else
x=z+1;
}
return rez;
}
int getnewpoz(int poz,int count, int NrLeft)
{
int nrstanga=getnr(poz),nr_caut=count;
if (count>NrLeft)
nr_caut=count-NrLeft*((count-1)/NrLeft);
if (nr_caut>NrLeft-nrstanga)
return search(nr_caut-NrLeft+nrstanga); else
return search(nr_caut+nrstanga);
}
int main()
{
int i,poz=1;
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i) update(i);
for (i=1;i<=n;++i)
{
poz=getnewpoz(poz,i,n-i+1);
printf("%d ",poz);
if (i==n) break;
del(poz);
}
return 0;
}