Pagini recente » Cod sursa (job #3279307) | Cod sursa (job #2762864) | Cod sursa (job #2160463) | Cod sursa (job #1450308) | Cod sursa (job #2751422)
#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;
}