Cod sursa(job #2750283)

Utilizator alexbrinzaAlexandru Brinza alexbrinza Data 10 mai 2021 17:20:45
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

vector < int > pre;
long long n, k, ct;

bool check(int left, int right)
{
    if(left >= right) return true;

    int index = left + 1;

    while(index <= right && pre[index] < pre[left]) ++index;

    for(int i = index; i <= right; ++i)
        if(pre[i] < pre[left]) return false;

    bool ok = check(left + 1, index - 1);
    if(ok == false) return false;

    ok = check(index, right);
    return ok;

}

void Preorder(int N) {

    for(int i = 1; i <= N; ++i)
        pre.push_back(i);

    do{
        if(check(0, N - 1))
        {
            ++ct;

            if(ct == k)
            {
                for(int i = 0; i < N; ++i)
                    out << pre[i] << " ";
                break;
            }
        }

    } while(next_permutation(pre.begin(), pre.end()));

}

int main()
{
    in >> n >> k;
    Preorder(n);
    return 0;
}