Cod sursa(job #2751828)

Utilizator Costin_PintilieHoratiu-Costin-Petru Pintilie Costin_Pintilie Data 15 mai 2021 21:42:19
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>
using namespace std;
/* https://www.geeksforgeeks.org/check-if-a-given-array-can-represent-preorder-traversal-of-binary-search-tree/
Do following for every node pre[i] starting from first one.
1) Find the first greater value on right side of current node.
   Let the index of this node be j. Return true if following
   conditions hold. Else return false
    (i)  All values after the above found greater value are
         greater than current node.
    (ii) Recursive calls for the subarrays pre[i+1..j-1] and
         pre[j+1..n-1] also return true.*/

vector<int> v;
bool preorder( int st, int dr){
    if(st >= dr)
        return 1;

    int i;
    for(i = st+1 ; i <= dr; i++){
        if (v[i] > v[st])
        break;}

    for(int j = i; j <= dr; j++){
        if(v[j]< v[st])
            return 0;}

    return preorder(st+1, i-1) && preorder(i, dr);

}

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

    do{
        if(preorder(0,N-1)){
            for(int j = 0 ; j < N; j++)
                cout<<v[j]<<" ";
            cout<<endl;
        }

    }while( next_permutation( v.begin(),v.end() ) );
}
ifstream fin("planeta.in");
ofstream fout("planeta.out");
int N,k;
int main() {
    fin >> N>>k;
    for(int i = 1; i <= N; i++)
    v.push_back(i);

    do{
        if(preorder(0,N-1)){
            k--;
            if(!k){
                for(int j = 0 ; j < N; j++)
                fout<<v[j]<<" ";
            return 0;
            }
        }

    }while( next_permutation( v.begin(),v.end() ) );
fin.close();
fout.close();
    return 0;
}