Pagini recente » Cod sursa (job #685399) | Cod sursa (job #1766983) | Cod sursa (job #2944719) | Cod sursa (job #2348223) | Cod sursa (job #1425375)
#include <cstdio>
using namespace std;
const int nmax=30000;
int n;
int aib[nmax+5];
int sol[nmax+5];
inline int lsb(int x)
{
return x&-x;
}
void update(int pos, int val)
{
for(int i=pos; i<=n; i+=lsb(i))
aib[i] += val;
}
int querry(int pos)
{
int ans=0;
for(int i=pos; i>0; i-=lsb(i))
ans+=aib[i];
return ans;
}
int binary(int x, int y, int val)
{
int last;
int ans = 0, sc = 0;
int t=querry(x-1);
for(int i=1<<17; i>0; i>>=1)
if(ans+i<=n)
{
if(sc+aib[ans+i]-t<val)
{
ans+=i;
sc+=aib[ans];
}
else if(sc+aib[ans+i]-t==val)
last=ans+i;
}
return last;
}
int main()
{
freopen("order.in", "r", stdin);
freopen("order.out", "w", stdout);
scanf("%d", &n);
for(int i=1; i<=n; i++)
update(i, 1);
int pos = 1;
for(int i=1; i<=n; i++)
{
int lg = (i-1) % (n-i+1) + 1;
int limit = querry(n) - querry(pos);
if(lg<=limit)
pos = binary(pos+1, n, lg);
else pos = binary(1, pos, lg-limit);
update(pos, -1);
printf("%d ", pos);
}
return 0;
}