Pagini recente » Cod sursa (job #2563124) | Cod sursa (job #2960364) | Cod sursa (job #387938) | Cod sursa (job #1377454) | Cod sursa (job #2986541)
#include <fstream>
#define lsb(x) x & (-x)
using namespace std;
ifstream cin ("order.in");
ofstream cout ("order.out");
const int N = 3e4;
int aib[N * 2 + 2], f[N + 1];
int n;
void update (int pos, int val)
{
for (int i = pos; i <= (n << 1); i += lsb(i))
aib[i] += val;
}
int query (int pos)
{
int s = 0;
for (int i = pos; i >= 1; i -= lsb(i))
s += aib[i];
return s;
}
int cb (int st, int dr, int pos)
{
int last, med;
int val = query (pos);
while (st <= dr)
{
med = (st + dr) >> 1;
if (query (med) - val < med - pos)
{
dr = med - 1;
last = med;
}
else
st = med + 1;
}
return last;
}
int cb1 (int st, int dr, int val, int pos)
{
int last, med;
int val1 = query (pos);
while (st <= dr)
{
med = (st + dr) >> 1;
if (med - pos - (query (med) - val1) >= val)
{
dr = med - 1;
last = med;
}
else
st = med + 1;
}
return last;
}
int main()
{
cin >> n;
int nrcop = n, pos = 1, ratie = 1;
while (nrcop)
{
if (f[pos])
{
int part = cb (pos + 1, (n << 1), pos);
if (part > n)part -= n;
pos = part;
}
int r;
if (nrcop == n)
r = ratie % nrcop;
else
r = (ratie - 1) % nrcop;
if (r)
{
int part = cb1 (pos + 1, (n << 1), r, pos);
pos = part;
if (pos > n) pos -= n;
cout << pos << ' ';
f[pos] = 1;
update (pos, 1);
update (pos + n, 1);
}
else
{
cout << pos << ' ';
f[pos] = 1;
update (pos, 1);
update (pos + n, 1);
}
--nrcop;
++ratie;
}
return 0;
}