Pagini recente » Cod sursa (job #384755) | Cod sursa (job #1877140) | Cod sursa (job #880929) | Cod sursa (job #2347645) | Cod sursa (job #2769770)
#include <fstream>
using namespace std;
const int NMAX = 30000;
int n;
int aib[1 + NMAX];
int ord[1 + NMAX];
inline int lsb(const int val)
{
return val & -val;
}
int query(int i)
{
int sol = 0;
for (; i > 0; i -= lsb(i))
sol += aib[i];
return sol;
}
void update(int i, int val)
{
for (; i <= n; i += lsb(i))
aib[i] += val;
}
int caut(int val)
{
int sol = 0;
int pow2 = 1;
while (pow2 * 2 <= n)
pow2 *= 2;
for (; pow2 > 0; pow2 >>= 1)
{
int pos = sol + pow2;
if (pos <= n && aib[pos] < val)
{
sol = pos;
val -= aib[pos];
}
}
sol++;
return sol;
}
int main()
{
ifstream in("order.in");
ofstream out("order.out");
in >> n;
for (int i = 1; i <= n; i++)
{
aib[i] += 1;
if (i + lsb(i) <= n)
aib[i + lsb(i)] += aib[i];
}
int pos = 1;
for (int i = 1; i <= n; i++)
{
int ramase = n - i + 1;
int nrPasi = query(pos) + i % ramase;
if (nrPasi > ramase)
nrPasi -= ramase;
if (nrPasi == 0)
nrPasi = ramase;
pos = caut(nrPasi);
update(pos, -1);
ord[i] = pos;
}
for (int i = 1; i <= n; i++)
out << ord[i] << ' ';
out << '\n';
return 0;
}