Cod sursa(job #3165722)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 6 noiembrie 2023 19:59:13
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.45 kb
#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);
    }
}