Pagini recente » Cod sursa (job #790201) | Cod sursa (job #842705) | Cod sursa (job #3151673) | Cod sursa (job #983109) | Cod sursa (job #975994)
Cod sursa(job #975994)
#include <iostream>
#include <fstream>
using namespace std;
#ifdef INFOARENA
ifstream fin("order.in");
ofstream fout("order.out");
#define cin fin
#define cout fout
#endif
const int maxn = 30100;
int n;
int aib[maxn];
inline void update(int position, int value)
{
for (int i = position; i <= n; i = (i | (i - 1)) + 1)
aib[i] += value;
}
inline int start_query(int position)
{
int res = 0;
for (int i = position; i >= 1; i = i & (i - 1))
res += aib[i];
return res;
}
inline int query(int start, int finish)
{
return start_query(finish) - start_query(start - 1);
}
inline int binsrc(int elements, int add)
{
int i = 0, cnt = 1 << 16, sum = -add;
for (; cnt; cnt >>= 1)
if (i + cnt <= n && sum + aib[i + cnt] < elements)
sum += aib[i += cnt];
return i + 1;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
update(i, 1);
for (int i = 1, le = n, rem = 1; i <= n; i++, le--)
{
int hm = i % le + (le == 1), foo = query(rem + 1, n);
//cout << i << ": " << rem << ' ' << foo << ' ' << hm << ' ' << le << '\n';
if (foo >= hm)
{
int add = query(1, rem);
rem = binsrc(hm, add);
}
else
{
hm -= foo;
rem = binsrc(hm, 0);
}
cout << rem << ' ';
update(rem, -1);
}
}