Pagini recente » Cod sursa (job #505190) | Cod sursa (job #2722904) | Cod sursa (job #55572) | Cod sursa (job #2961623) | Cod sursa (job #3165722)
#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const long long INF = 1000000000000000000;
const int mod = 1e9 + 7;
const char out[2][4]{ "NO", "YES" };
#define all(A) A.begin(), A.end()
using ll = long long;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
#define variableName(var) #var
#define __debug(var) cout << #var << " = " << var << '\n'
inline int rint(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
class fenwick {
private:
vector<int> t;
int size;
void add(int i, int x) {
for (; i <= size; i += i & -i) {
t[i] += x;
}
}
int get(int i) {
int sum = 0;
for (; i > 0; i -= i & -i) {
sum += t[i];
}
return sum;
}
public:
void build(int size) {
this->size = size;
t.resize(size + 1);
for (int i = 1; i <= size; ++i) {
add(i, 1); // marchez elementul i ca existent
}
}
void erase(int i) {
add(i, -1);
}
int less_than(int i) {
return get(i - 1);
}
};
long long maxinv(int len) {
return len * (len - 1) / 2;
}
int n, lg = 0;
long long k;
fenwick tree;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fin >> n >> k;
while ((1 << (lg + 1)) <= n) {
lg++;
}
tree.build(n);
for (int i = 1; i <= n; ++i) {
// cautam cel mai mic element astfel incat
// tree.less_than() + maxinv(n - i) >= k
// noile inversiuni + numarul maxim de inversiuni pe care putem
// sa le facem cu cele ramase >= numarul necesar de inversiuni
int st = 1, dr = n, j = -1;
while (st <= dr) {
int mid = (st + dr) / 2;
if (tree.less_than(mid) + maxinv(n - i) >= k) {
j = mid, dr = mid - 1;
}
else {
st = mid + 1;
}
}
// mutam pozitia pana ajunge intr-una marcata ca existenta in aib
for (int p = lg; p >= 0; --p) {
if (j + (1 << p) <= n && tree.less_than(j + (1 << p)) == tree.less_than(j)) {
j += (1 << p);
}
}
fout << j << sp;
k -= tree.less_than(j);
tree.erase(j);
}
}