Pagini recente » Cod sursa (job #1132271) | Cod sursa (job #1855552) | Cod sursa (job #2965598) | Statistici Zanet Doru (doru.zanet) | Cod sursa (job #2010001)
#include <stdio.h>
#define MAXN 100000
#define Inversions(x) ((x) * ((x) - 1) / 2)
#define LeftSon(x) ((x) << 1)
#define RightSon(x) (((x) << 1) + 1)
typedef long long int64;
int64 seg[4 * MAXN + 4];
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(int node, int left, int right, int pos)
{
if (left == right) {
seg[node] = 1;
return;
}
int mid = left + (right - left) / 2;
if (pos <= mid) {
Update(LeftSon(node), left, mid, pos);
} else {
Update(RightSon(node), mid + 1, right, pos);
}
seg[node] = seg[LeftSon(node)] + seg[RightSon(node)];
}
int64 GetByOrder(int node, int left, int right, int order)
{
if (left == right) {
return left;
}
int mid = left + (right - left) / 2;
int left_len = mid - left + 1;
if (left_len - seg[LeftSon(node)] >= order) {
return GetByOrder(LeftSon(node), left, mid, order);
}
order -= (left_len - seg[LeftSon(node)]);
return GetByOrder(RightSon(node), mid + 1, right, order);
}
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, 1, n, 1);
} else {
int64 order = GetOrder(inv, n - i);
number = GetByOrder(1, 1, n, order);
inv -= (order - 1);
}
Update(1, 1, n, number);
fprintf(fout, "%lld ", number);
}
return 0;
}