Pagini recente » Cod sursa (job #1520995) | Cod sursa (job #1119312) | Cod sursa (job #1773222) | Cod sursa (job #3241925) | Cod sursa (job #2555046)
#include <bits/stdc++.h>
#define lsb(x) ((x ^ (x - 1)) & x)
#define Nmax 30005
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int N;
int bit[Nmax];
int pos = 0;
bool vis[Nmax];
void update(int pos, int val)
{
for(; pos <= N; pos += lsb(pos))
bit[pos] += val;
}
int query(int pos)
{
int ret = 0;
for(; pos >= 1; pos -= lsb(pos))
ret += bit[pos];
return ret;
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
update(i, 1);
int cnt = 1, pos = 1, add = 0, idx = 0, sum = 0;
for(int i = 1; i < N;)
{
if(add == 0)
add = 1 + (i - 1) % (N - i + 1);
idx = pos;
for(int le = pos, ri = N; le <= ri;)
{
int mid = (le + ri) / 2;
if(query(mid) - cnt < add)
{
idx = mid;
le = mid + 1;
}
else
ri = mid - 1;
}
sum = query(idx);
if(idx == N)
{
add -= sum - cnt;
pos = 0;
cnt = 0;
}
else
{
pos = idx + 1;
fout << pos << " ";
vis[pos] = true;
update(pos, -1);
cnt = query(pos);
add = 0;
i++;
}
}
for(int i = 1; i <= N; i++)
if(!vis[i])
fout << i << "\n";
return 0;
}