Cod sursa(job #2746323)

Utilizator icnsrNicula Ionut icnsr Data 27 aprilie 2021 18:08:35
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <fstream>
std::ifstream fin("planeta.in");
std::ofstream fout("planeta.out");

#include <vector>
#include <limits>

using u64 = std::uint64_t;
constexpr u64 NOTSET = std::numeric_limits<u64>::max();

class Factorial
{
public:
        static 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];
        }

        static std::vector<u64> values;
};

std::vector<u64> Factorial::values = {1, 1, 2};

u64 catalan(const u64 n)
{
        u64 p1 = 1u;
        for(u64 i = n + 2u; i <= 2u * n; ++i)
        {
                p1 *= i;
        }

        return p1 / Factorial::get(n);
}

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 solve(const u64 left, const u64 right, const u64 target, const u64 sofar)
{
        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 = solve(left, found - 1, target, sofar + getpossible(left, found, right));
        solve(found + 1, right, target, l1);

        return sofar + getpossible(left, found, right);
}

int main()
{
        u64 N, K;
        fin >> N >> K;
        solve(1, N, K, 0);
        fout << '\n';
}