Pagini recente » Cod sursa (job #1456674) | Cod sursa (job #2237264) | Cod sursa (job #1071796) | Cod sursa (job #232137) | Cod sursa (job #474010)
Cod sursa(job #474010)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 128000
int n;
int inv[MAXN];
int rt[4 * MAXN];
FILE *f;
long long k;
int get_and_mark(int node, int ord, int st, int en) {
++rt[node];
if (st + 1 == en) return st;
int mid = (st + en) / 2;
int left_node = node * 2 + 1;
int right_node = node * 2 + 2;
int av_left = mid - st - rt[left_node];
if (av_left > ord) {
return get_and_mark(left_node, ord, st, mid);
} else {
return get_and_mark(right_node, ord - av_left, mid, en);
}
}
int main() {
f = fopen("farfurii.in", "rt");
fscanf(f, "%d %lld", &n, &k);
fclose(f);
inv[n - 1] = 0;
for (int i = n - 2; i >= 0; --i) {
int max = n - i - 1;
if (k < max) max = k;
inv[i] = max;
k -= max;
}
memset(rt, 0, sizeof(rt));
f = fopen("farfurii.out", "wt");
for (int i = 0; i < n; ++i) {
inv[i] = get_and_mark(0, inv[i], 0, n);
fprintf(f, "%d ", inv[i] + 1);
}
fprintf(f, "\n");
fclose(f);
return 0;
}