Cod sursa(job #2898208)

Utilizator widzAndrei-Daniel Tava widz Data 6 mai 2022 12:15:03
Problema Planeta Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <array>
using namespace std;



//ma doare fizic sa fac functii si variabile globale
//dar altfel recursia ar fi foarte greu de facut
// si mi-e lene sa fac iterativ acum
array<int, 30> preorder;
array<pair<int, int>, 30> ranges;
array<long long, 31> catalanNrs;
ifstream in("planeta.in");
ofstream out("planeta.out");
void afis(int n)
{

	for (int i = 0; i < n; ++i)
		out << preorder[i] << " ";
}
void kthPreorder(int pos,long long k)
{
	static long long count = 0;
	const int lower_bound = ranges[pos].first;
	const int upper_bound = ranges[pos].second;
	for(int i = lower_bound; i < upper_bound; ++i)
	{
		if (count == k)
		{
			afis(ranges[0].second);
			exit(0);
		}
		preorder[pos] = i + 1;
		if (pos == ranges[0].second - 1)
			++count;
		if(i - lower_bound > 0)
			ranges[pos + 1] = { lower_bound, i};
		if(upper_bound- i - 1 > 0)
			ranges[pos + i - lower_bound + 1] = { i + 1, upper_bound };
		kthPreorder(pos + 1, k);
	}
}
void computeCatalan(int n)
{

	catalanNrs[0] = catalanNrs[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		catalanNrs[i] = 0;
		for (int j = 0; j < i; ++j)
			catalanNrs[i] += catalanNrs[j] * catalanNrs[i - j - 1];
	}
}


int main()
{
	int n;
	long long k;
	in >> n >> k;
	in.close();
	computeCatalan(n);
	ranges[0] = {0,n};
	kthPreorder(0,k);
	return 0;
}