Pagini recente » Cod sursa (job #2974568) | Cod sursa (job #2775192) | În grupurile apei, un joc secund, mai pur. | Cod sursa (job #2350466) | Cod sursa (job #2926232)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("order.in");
ofstream fout ("order.out");
const int nMAX = 30e3;
int n;
int aib[nMAX + 1]; // aib[i] = cate elemente nu sunt sterse in intervalul [i - (i&-i) + 1, i]
void buildAib()
{
for (int i = 1; i <= n; ++i)
{
aib[i] += 1;
if (i + (i&-i) <= n)
aib[i + (i&-i)] += aib[i];
}
}
void addAib(int pos, int val)
{
for (; pos <= n; pos += pos & -pos)
aib[pos] += val;
}
int queryAib(int dr)
{
int sum = 0;
for (; dr >= 1; dr -= dr & -dr)
sum += aib[dr];
return sum;
}
int bsAib(int val) // returneaza pozitia pos minima pentru care queryAib(pos) = val
{
int pos = 0, sum = 0;
for (int i = 31-__builtin_clz(n); i >= 0; --i)
{
if ((pos | (1<<i)) < n && sum + aib[pos | (1<<i)] < val)
{
pos |= 1<<i;
sum += aib[pos];
}
}
return pos+1;
}
int main()
{
fin >> n;
buildAib();
int pos = 1;
for (int i = 1; i <= n; ++i)
{
int inou = i % (n-i+1);
int ramase = queryAib(pos); // cate elemente au ramas in intervalul [1, pos]
if (ramase + inou == 0)
pos = bsAib(n-i+1);
else if (ramase + inou <= n-i+1)
pos = bsAib(ramase + inou);
else // ramase + inou > n-i+1
pos = bsAib(ramase + inou - (n-i+1));
addAib(pos, -1);
fout << pos << ' ';
}
}