Cod sursa(job #2746233)

Utilizator icnsrNicula Ionut icnsr Data 27 aprilie 2021 17:13:52
Problema Planeta Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#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';
}