Submission #433610

#	Time	Username	Problem	Language	Result	Execution time	Memory
433610		Lam_lai_cuoc_doi	K-th path (IZhO11_kthpath)	C++17	0 / 100	1 ms	204 KiB

kthpath

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 30 + 2;
int m, n;
int x[] = {0, 1},
    y[] = {1, 0};
string s[N];
ll dp[N][N], k;

void Read()
{
    cin >> m >> n;

    for (int i = 1; i <= m; ++i)
    {
        cin >> s[i];
        s[i] = " " + s[i];
    }

    cin >> k;
}

void BFS(int x, int y)
{
    queue<pair<int, int>> s;
    dp[x][y] = 1;
    s.emplace(x, y);

    while (s.size())
    {
        auto c = s.front();
        s.pop();

        if (c.first > 1)
        {
            if (!dp[c.first - 1][c.second])
                s.emplace(c.first - 1, c.second);
            dp[c.first - 1][c.second] += dp[c.first][c.second];

            if (dp[c.first - 1][c.second] > 1e18)
                dp[c.first - 1][c.second] = 2e18;
        }
        if (c.second > 1)
        {
            if (!dp[c.first][c.second - 1])
                s.emplace(c.first, c.second - 1);
            dp[c.first][c.second - 1] += dp[c.first][c.second];

            if (dp[c.first][c.second - 1] > 1e18)
                dp[c.first][c.second - 1] = 2e18;
        }
    }
}

void Solve()
{
    BFS(m, n);

    int a(1), b(1);

    while (a != m || b != n)
    {
        cout << s[a][b];
        if (a == m)
            ++b;
        else if (b == n)
            ++a;
        else
        {
            int d[] = {0, 1};
            if (s[a + x[d[0]]][b + y[d[0]]] > s[a + x[d[1]]][b + y[d[1]]])
                swap(d[0], d[1]);

            if (dp[a + x[d[0]]][b + y[d[0]]] >= k)
            {
                a += x[d[0]];
                b += y[d[0]];
            }
            else
            {
                k -= dp[a + x[d[0]]][b + y[d[0]]];

                a += x[d[1]];
                b += y[d[1]];
            }
        }
    }

    cout << s[a][b];
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

• Subtask 1: 0 / 100