Cod sursa(job #2751422)

Utilizator mentolnothingmoreNegrut Maria Daniela mentolnothingmore Data 14 mai 2021 23:02:07
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> result;
int counter, N , K;

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

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

    int index_current_right = left + 1; // the closest right index
    while (index_current_right <= right)
    {
        if (result[index_current_right] > result[left]) break;
        index_current_right ++;
    }

    int checking_right_side = index_current_right + 1;
    while (checking_right_side <= right)
    {
        if (result[checking_right_side] < result[left]) return 0;
        // nu e format corect am in ramura din dreapta "radacinii" valori mai mici
        checking_right_side ++;
    }

    return check(left + 1, index_current_right - 1) && check(index_current_right, right);
}

void print()
{
    for (int i = 0; i < result.size(); ++i)
        fout << result[i] << " ";
    fout << "\n";
}

template<typename It> // not my code
// javatpoint C++ Algorithm next_permutation ()
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
        ++i;
        if (i == end)
                return false;

        i = end;
        --i;

        while (true)
        {
                It j = i;
                --i;

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin)
                {
                        reverse(begin, end);
                        return false;
                }
        }
}


void allBstPreorders(int N) {
    for (int i = 1; i <= N; ++i) result.push_back(i);
    do
    {

        if (check(0, N - 1) == 1) counter++;
        if (counter == K)
        {
            print();
            break;
        }

    } while (::next_permutation(result.begin(), result.end()));
}

int main()
{
    fin >> N >> K;
    allBstPreorders(N);

    return 0;
}