Cod sursa(job #2428689)

Utilizator topala.andreiTopala Andrei topala.andrei Data 6 iunie 2019 01:35:14
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
// Determinarea permutarii de lungime N cu K inversuri
// minima lexicografic O(N*logN)
#include <iostream>
#include <fstream>
#define INF 1<<30
#define MAXN 100001
using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
long long N, K, maxInv;
long long arbInt[5 * MAXN], qAns;
void update(int node, int pos, int value, int left, int right) {
    if (left == right) {
        arbInt[node] += value;
        return;
    }
    int mid = (left + right) / 2;
    if (pos <= mid) {
        update(2 * node, pos, value, left, mid);
    } else {
        update(2 * node + 1, pos, value, mid + 1, right);
    }
    arbInt[node] = arbInt[2 * node] + arbInt[2 * node + 1];
}
void querry(int node, int K, int left, int right) {
    if (left == right) {
        qAns = left;
        return;
    }
    int mid = (left + right) / 2;
    if (K <= arbInt[2 * node]) {
        querry(2 * node, K, left, mid);
    } else {
        querry(2 * node + 1, K - arbInt[2  * node], mid + 1, right);
    }
}
int main()
{
    f >> N >> K;
    for (int i = 1; i <= N; ++i) {
        update(1, i, 1, 1, N);
    }
    for (int i = 1; i <= N; ++i) {
        maxInv = (N - i)*(N - i - 1) / 2;
        if (K <= maxInv) {
            querry(1, 1, 1, N);
            update(1, qAns, -1, 1, N);
            g << qAns << ' ';
        } else {
            qAns = INF;
            querry(1, K - maxInv + 1, 1, N);
            update(1, qAns, -1, 1, N);
            g << qAns << ' ';
            K = maxInv;
        }
    }
    return 0;
}