Pagini recente » Cod sursa (job #801565) | Cod sursa (job #2154287) | Cod sursa (job #1638957) | Cod sursa (job #1109371) | Cod sursa (job #2746233)
#include <fstream>
std::ifstream fin("arbori2.in");
std::ofstream fout("arbori2.out");
#include <vector>
#include <limits>
using u64 = std::uint64_t;
constexpr u64 NOTSET = std::numeric_limits<u64>::max();
class Factorial
{
public:
u64 get(const u64 n)
{
if(n >= values.size())
{
values.resize(n + 1, NOTSET);
}
if(values[n] == NOTSET)
{
const u64 val = n * get(n - 1);
values[n] = val;
}
return values[n];
}
private:
std::vector<u64> values = {1, 1, 2};
};
u64 catalan(const u64 n)
{
static Factorial fact;
const auto p1 = fact.get(2u * n);
const auto p2 = fact.get(n + 1u);
const auto p3 = fact.get(n);
return p1 / (p2 * p3);
}
u64 getpossible(const u64 left, const u64 rootlim, const u64 right)
{
u64 res = 0;
for(u64 i = left; i < rootlim; ++i)
{
res += catalan(i - left) * catalan(right - i);
}
return res;
}
u64 foo(const u64 left, const u64 right, const u64 target, const u64 sofar = 0)
{
// fout << "l/r/t/sf " << left << ' ' << right << ' ' << target << ' ' << sofar
//<< '\n';
if(left > right)
{
return sofar;
}
if(left == right)
{
fout << left << ' ';
return sofar;
}
u64 start = left;
while(start <= right)
{
const u64 minidx = getpossible(left, start, right);
if(sofar + minidx >= target)
{
break;
}
++start;
}
const u64 found = start - 1;
fout << found << ' ';
const u64 l1 = foo(left, found - 1, target, sofar + getpossible(left, found, right));
foo(found + 1, right, target, l1);
return sofar + getpossible(left, found, right);
}
int main()
{
u64 N, K;
fin >> N >> K;
foo(1, N, K, 0);
fout << '\n';
}