Cod sursa(job #3135464)

Utilizator iulia_tamasTamas Iulia iulia_tamas Data 3 iunie 2023 12:45:53
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb

#include<bits/stdc++.h>
using namespace std;
ifstream fin("planeta.in");
ofstream fout("planeta.out");
//const int nmax = (int)1e9 + 7;
int n,x[100], nr;
vector<long long>y;
vector<vector<long long>>yy;
long long m;

bool preordine(vector<long long>& preord){
    stack<int> st;
    long long top=INT_MIN;
    for(int i=0; i<preord.size(); i++){
        if(preord[i]<top){
            return false;
        }
        while(!st.empty() and preord[i]>st.top()){
            top=st.top();
            st.pop();
        }
        st.push(preord[i]);
    }
    return true;
}


void afisare(){
    y.clear();
    for(int j=1;j<=n;j++)
        y.push_back(x[j]);
    if(preordine(y)==true){
        nr++;
    }
    //cout<<endl;
}

bool notin(int k){
    for(int i=1;i<k;++i)
        if(x[k]==x[i])
            return false;
    return true;
}

void back(int k){
    if(nr<m){
    for(int i=1; i<=n; i++){
        x[k]=i;
        if(notin(k)){
            if(k==n){
                afisare();
                //cout<<nr<<endl;
                }
            else
                back(k+1);
        }
    }
    }
}

/*bool preordine(vector<long long>& preord){
    stack<int> st;
    long long top=INT_MIN;
    for(int i=0; i<preord.size(); i++){
        if(preord[i]<top){
            return false;
        }
        while(!st.empty() and preord[i]>st.top()){
            top=st.top();
            st.pop();
        }
        st.push(preord[i]);
    }
    return true;
}*/

/*void permutare(string &a, int st, int dr){

    if(st==dr)
        cout<<a<<endl;
    else{
        for(int i=st; i<=dr; i++){
            swap(a[st],a[dr]);
            permutare(a,st+1,dr);
            swap(a[l],a[i]);
        }
    }
}*/


int main(){
    fin>>n>>m;
    back(1);
    long long d=0;
    for(int i=0; i<y.size(); i++){
        fout<<y[i]<<' ';
    }




   /*for(int i=0; i<yy.size(); i++){
        for(int j=0; j<yy[i].size(); j++)
            cout<<yy[i][j];
        cout<<' '<<preordine(yy[i])<<endl;
        if(preordine(yy[i])) d++;
    }
    cout<<d;*/
    /*long long i=0;
    while(i<yy.size() and d<m){
        if(preordine(yy[i])) d++;
        i++;
    }
    //cout<<i;
    for(int j=0; j<yy[i-1].size(); j++)
        cout<<yy[i-1][j]<<' ';
*/

return 0;
}