Submission #488971

#	Time	Username	Problem	Language	Result	Execution time	Memory
488971		SirCovidThe19th	K-th path (IZhO11_kthpath)	C++17	100 / 100	1 ms	336 KiB

kthpath

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define f first
#define s second

int n, m; ll k, ways[35][35], choose[75][75]; string A[35];
pll range[35][35], par[35][35];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> A[i], A[i] = " " + A[i];
    cin >> k;

    for (int i = 0; i < 75 and (choose[i][0] = 1); i++)
        for (int j = 1; j <= i; j++)
            choose[i][j] = choose[i - 1][j] + choose[i - 1][j - 1];

    ways[1][1] = 1; range[1][1] = {1, choose[n + m - 2][n - 1]}; 

    for (int len = 2; len <= n + m - 1; len++){
        unordered_map<ll, vector<pll>> mp;
        for (int i = min(len, n), j = max(len - n + 1, 1); i and j <= m; i--, j++){
            if (ways[i - 1][j]) range[i][j] = range[i - 1][j], par[i][j] = {i - 1, j};
            if (ways[i][j - 1]) range[i][j] = range[i][j - 1], par[i][j] = {i, j - 1};
            ways[i][j] += ways[i - 1][j] + ways[i][j - 1];
            if (ways[i][j]) mp[range[i][j].f].push_back({i, j});
        }
        for (auto X : mp){
            vector<pll> V = X.s; ll rangeST = X.f; 
            for (char c = 'a'; c <= 'z'; c++){
                ll tot = 0;
                for (pll i : V) if (A[i.f][i.s] == c){
                    tot += ways[i.f][i.s] * choose[(n - i.f) + (m - i.s)][(m - i.s)];
                }
                for (pll i : V) if (A[i.f][i.s] == c){
                    range[i.f][i.s] = {rangeST, rangeST + tot - 1};
                    if (k < rangeST or k > rangeST + tot - 1) ways[i.f][i.s] = 0;
                }
                rangeST += tot;
            }
        }
    }
    vector<char> ans; pll cur = {n, m};
    while (cur.f) ans.push_back(A[cur.f][cur.s]), cur = par[cur.f][cur.s];
    for (int i = ans.size() - 1; ~i; i--) cout<<ans[i];
}

• Subtask 1: 100 / 100