Cod sursa(job #3135390)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 3 iunie 2023 00:24:38
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
//ALEXANDRU MICLEA

#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>
#include <iostream>
#include <fstream>
#include <array>

using namespace std;

typedef long long ll;

//VARIABLES

long long catalane[35];

//FUNCTIONS

void solve(int left, int right, long long k) {
    // I have the nodes in range [left, right] to play with

    int node = left;

    for (int i = left; i <= right; i++){
        int lst = i - left;
        int rst = right - i;
        long long p = catalane[lst] * catalane[rst];

        // skip redundant subtrees
        if (p < k) k -= p;
        else {
            cout << i << ' ';
            if (i > left) {
                solve (left, i - 1, k / catalane[rst]);
            }
            if (i < right){
                solve(i + 1, right, k % catalane[rst]);
            }
            return;
        }
    }
}

//MAIN
int main() {

#ifdef INFOARENA
    ifstream fin("planeta.in"); ofstream fout("planeta.out");
    cin.rdbuf(fin.rdbuf()); cout.rdbuf(fout.rdbuf());
#endif

    catalane[0] = catalane[1] = 1;

    for (int i = 2; i <= 34; i++) {
        for (int j = 1; j <= i; j++) {
            catalane[i] += catalane[j - 1] * catalane[i - j];
        }
    }
    //cout << catalane[5];
    // for (int i = 1; i <= 5; i++) cout << catalane[i] << ' ';

    int n;
    long long k; 
    cin >> n >> k;

    solve (1, n, k);

    return 0;
}