Pagini recente » Cod sursa (job #1732128) | Cod sursa (job #1265747) | Cod sursa (job #992789) | Cod sursa (job #1295855) | Cod sursa (job #2009975)
#include <stdio.h>
#define MAXN 100000
typedef long long int64;
int64 inversions[MAXN + 1];
int bit[MAXN + 1];
int perm[MAXN];
int Lsb(int x) { return x & (-x); }
int GetOrder(int inv, int n)
{
int pos = 0;
int power = (1 << 18);
while (power > 0) {
if (pos + power < n && inv - (pos + power - 1) > inversions[n - 1]) {
pos += power;
}
power >>= 1;
}
return pos + 1;
}
void Update(int pos, int n)
{
while (pos <= n) {
++bit[pos];
pos += Lsb(pos);
}
}
int GetCount(int pos)
{
int count = 0;
while (pos > 0) {
count += bit[pos];
pos -= Lsb(pos);
}
return count;
}
int GetByOrder(int order, int n)
{
int pos = 0;
int power = (1 << 18);
while (power > 0) {
if (pos + power <= n && pos + power - GetCount(pos + power) < order) {
pos += power;
}
power >>= 1;
}
return pos + 1;
}
int main()
{
FILE *fin = fopen("farfurii.in", "r");
FILE *fout = fopen("farfurii.out", "w");
int n;
int64 inv;
fscanf(fin, "%d%lld", &n, &inv);
int i;
inversions[2] = 1;
for (i = 3; i <= n; ++i) {
inversions[i] = inversions[i - 1] + i - 1;
}
for (i = 0; i < n; ++i) {
int64 capacity = inversions[n - i - 1];
if (capacity >= inv) {
perm[i] = GetByOrder(1, n);
} else {
int order = GetOrder(inv, n - i);
perm[i] = GetByOrder(order, n);
inv -= (order - 1);
}
Update(perm[i], n);
}
for (i = 0; i < n; ++i) {
fprintf(fout, "%d ", perm[i]);
}
return 0;
}