Pagini recente » Cod sursa (job #2861064) | Cod sursa (job #2428661) | Cod sursa (job #1650933) | Cod sursa (job #714617) | Cod sursa (job #2947208)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 60004;
ifstream fin("order.in");
ofstream fout("order.out");
int n;
int nr_ramase;
struct BinaryIndexedTree
{
vector<int> bit;
void init()
{
bit.assign(n + 4, 0);
for (int i = 1; i <= n; i++)
{
add(i, 1);
}
}
void add(int idx, int value)
{
while (idx <= n)
{
bit[idx] += value;
idx += (idx & (-idx));
}
}
int sum(int idx)
{
int total = 0;
while (idx > 0)
{
total += bit[idx];
idx -= (idx & (-idx));
}
return total;
}
int range_sum(int left, int right)
{
return sum(right) - sum(left - 1);
}
} BIT;
int main()
{
fin >> n;
BIT.init();
int nrc = 1;
nr_ramase = n;
for (int i = 1; i <= n; i++)
{
int p = 1;
int val = (nrc + (i % nr_ramase));
if (val > nr_ramase)
{
val -= nr_ramase;
}
while (p < n)
{
p <<= 1;
}
int j = 0;
nrc = val - 1;
nr_ramase--;
if (nrc < 1)
{
nrc += nr_ramase;
}
while (p)
{
if (j + p <= n && BIT.bit[j + p] < val)
{
val -= BIT.bit[j + p];
j += p;
}
p >>= 1;
}
fout << j + 1 << ' ';
BIT.add(j + 1, -1);
}
fin.close();
fout.close();
return 0;
}