Cod sursa(job #3234788)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 11 iunie 2024 18:45:27
Problema Planeta Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Funcție pentru a insera un nod într-un BST
TreeNode* insertBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = insertBST(root->left, val);
    else root->right = insertBST(root->right, val);
    return root;
}

// Funcție pentru a genera traversarea în pre-ordine a unui BST
void preOrderTraversal(TreeNode* root, vector<int>& traversal) {
    if (!root) return;
    traversal.push_back(root->val);
    preOrderTraversal(root->left, traversal);
    preOrderTraversal(root->right, traversal);
}

// Funcție pentru a genera toate permutările și a construi BST-urile
void generatePermutations(int N, int K, vector<int>& result) {
    vector<int> nums(N);
    iota(nums.begin(), nums.end(), 1);  // Umplem nums cu 1, 2, ..., N
    vector<vector<int>> traversals;

    do {
        TreeNode* root = NULL;
        for (int num : nums) {
            root = insertBST(root, num);
        }
        vector<int> traversal;
        preOrderTraversal(root, traversal);
        traversals.push_back(traversal);
    } while (next_permutation(nums.begin(), nums.end()));

    // Sortăm traversările în pre-ordine lexicografic
    sort(traversals.begin(), traversals.end());

    // Returnăm a K-a traversare în pre-ordine
    result = traversals[K - 1];
}

int main() {
    ifstream inFile("planeta.in");
    ofstream outFile("planeta.out");

    int N, K;
    inFile >> N >> K;

    vector<int> result;
    generatePermutations(N, K, result);

    for (int val : result) {
        outFile << val << " ";
    }
    outFile << endl;

    return 0;
}