Pagini recente » Cod sursa (job #459367) | Cod sursa (job #1614245) | Cod sursa (job #1387000) | Cod sursa (job #1293187) | Cod sursa (job #2755181)
#include<fstream>
using namespace std;
int v[100000],a[100000],i,n,m,p,k;
void update(int k,int val)
{
int i;
for (i=k;i<=m;i=(i | (i-1))+1)
v[i]+=val;
}
int query(int k)
{
int i,s=0;
for (i=k;i>0;i=i & (i-1))
s+=v[i];
return s;
}
int search(int k)
{
int i,t=0;
for (i=m;i>=1;i/=2)
if ((v[i/2+t]<=k) && (i/2+t<=n))
{
k-=v[i/2+t];
t+=i/2;
}
return t;
}
int main()
{
ifstream f("order.in");
ofstream g("order.out");
f >> n;i=n;m=1;
while (i>0)
{
i/=2;
m*=2;
}
for (i=1;i<=n;i++)
update(i,1);
p=1;k=1;
for (i=1;i<=n;i++)
{
p=search((k+i-1)%(n-i+1)+1);
while (a[p]==1)
{
p--;
if (p==0)
p=n;
}
g << p << ' ';
update(p,-1);
a[p]=1;
k=query(p);
}
return 0;
}