Cod sursa(job #3132379)

Utilizator Nicoleta114Caramaliu Nicoleta Nicoleta114 Data 22 mai 2023 16:25:32
Problema Planeta Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

ifstream f("planeta.in");
ofstream g("planeta.out");

vector<long long> catalan_nr(int n) {
    vector<long long> catalan(n + 1, 0);
    catalan[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            catalan[i] += catalan[j] * catalan[i - j - 1];
        }
    }

    return catalan;
}

string gasesteK(vector<int>& perm, const vector<long long>& catalan, int start, int end, long long k) {
    if (start > end) {
        return "";
    }

    int rIndex = start;
    while (rIndex < end && k >= catalan[rIndex - start] * catalan[end - rIndex - 1]) {
        k -= catalan[rIndex - start] * catalan[end - rIndex - 1];
        rIndex++;
    }

    string t = to_string(perm[rIndex]) + " ";
    string leftT= gasesteK(perm, catalan, start, rIndex - 1, k / catalan[end - rIndex - 1]);
    string rightT = gasesteK(perm, catalan, rIndex + 1, end, k % catalan[end - rIndex - 1]);

    t += leftT + rightT;
    return t;
}

int main() {
    int N, K;
    f >> N >> K;

    vector<int> perm(N);
    for (int i = 0; i < N; i++) {
        perm[i] = i + 1;
    }

    vector<long long> catalan = catalan_nr(N);
    string resultat = gasesteK(perm, catalan, 0, N - 1, K - 1);

    g << resultat << endl;

    return 0;
}