Pagini recente » Diferente pentru eliminare-gaussiana intre reviziile 6 si 7 | Concursuri Virtuale | Istoria paginii blog/suma-15-solutie | Istoria paginii utilizator/dragonslover | Cod sursa (job #2019973)
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long LL;
#ifdef INFOARENA
#define ProblemName "farfurii"
#endif
#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif
const int MAXN = 100010;
int arbInt[MAXN << 2];
int N, arbSz;
inline int leftSon(int x) {
return x * 2 + 1;
}
inline int rightSon(int x) {
return x * 2 + 2;
}
inline int parent(int x) {
return (x - 1) >> 1;
}
void pre() {
arbSz = 1;
while (arbSz < N)
arbSz *= 2;
for (int i = 0; i < N; ++i)
arbInt[i + arbSz - 1] = 1;
for (int i = arbSz - 2; i >= 0; --i)
arbInt[i] = arbInt[leftSon(i)] + arbInt[rightSon(i)];
}
void update(int pos, int delta) {
pos += arbSz - 1;
while (pos >= 0) {
arbInt[pos] += delta;
pos = parent(pos);
}
}
int kthElement(int k) {
int cur = 0;
while (cur < arbSz - 1) {
if (arbInt[leftSon(cur)] <= k) {
k -= arbInt[leftSon(cur)];
cur = rightSon(cur);
}
else cur = leftSon(cur);
}
return cur - (arbSz - 1);
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OuFile, "w", stdout));
LL K;
scanf("%d%lld", &N, &K);
pre();
for (int i = 0; i < N; ++i) {
int r = N - i;
LL p = 1LL * (r - 2) * (r - 1) / 2;
int ith = 0;
if (p < K) {
ith = (int)(K - p);
K -= ith;
}
int true_ith = kthElement(ith);
update(true_ith, -1);
printf("%d ", true_ith + 1);
}
putchar('\n');
return 0;
}