Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/mihaichirculete | The Cat | Istoria paginii utilizator/denis98 | Cod sursa (job #2009984)
#include <stdio.h>
#define MAXN 100000
#define Inversions(x) ((x) * ((x) - 1) / 2)
#define Lsb(x) ((x) & -(x))
typedef long long int64;
int64 bit[MAXN + 1];
int64 GetOrder(int64 inv, int64 n)
{
int64 pos = 0;
int64 power = (1 << 17);
while (power > 0) {
if (pos + power < n && inv - (pos + power - 1) > Inversions(n - 1)) {
pos += power;
}
power >>= 1;
}
return pos + 1;
}
void Update(int64 pos, int64 n)
{
while (pos <= n) {
++bit[pos];
pos += Lsb(pos);
}
}
int64 GetCount(int64 pos)
{
int64 count = 0;
while (pos > 0) {
count += bit[pos];
pos -= Lsb(pos);
}
return count;
}
int64 GetByOrder(int64 order, int64 n)
{
int64 pos = 0;
int64 power = (1 << 17);
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");
int64 n, inv;
fscanf(fin, "%lld%lld", &n, &inv);
int64 i;
for (i = 0; i < n; ++i) {
int64 capacity = Inversions(n - i - 1);
int64 number = 0;
if (capacity >= inv) {
number = GetByOrder(1, n);
} else {
int64 order = GetOrder(inv, n - i);
number = GetByOrder(order, n);
inv -= (order - 1);
}
Update(number, n);
fprintf(fout, "%lld ", number);
}
return 0;
}