Submission #1286588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286588		_rain_	K-th path (IZhO11_kthpath)	C++17	0 / 100	1512 ms	327680 KiB

kthpath

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

#define sz(x) (int)(x).size()

const int N = (int) 100;
const int dx[] = {0 , 1};
const int dy[] = {1 , 0};

int numrow , numcol;
LL need_k;
LL C[N * 2 + 2][N + 2];
char a[N + 2][N + 2];


LL ways(int start_x , int start_y){
    int t1 = numrow - start_x + 1;
    int t2 = numcol - start_y + 1;
    return C[t1 + t2 - 2][t2 - 1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0) ; cout.tie(0);

    cin >> numrow >> numcol;
    for(int i = 1; i <= numrow; ++i){
        string s; cin >> s;
        s = '#' + s;
        for(int j = 1; j <= numcol; ++j) a[i][j] = s[j];
    }
    cin >> need_k;

    for(int i = 0; i <= numrow + numcol - 1; ++i) C[i][0] = 1;
    for(int i = 1; i <= numrow + numcol - 1; ++i){
        for(int j = 1; j <= min(i , max(numrow , numcol)); ++j){
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }   
    }
    
    vector<pair<int,int>> cur_pos;
    cur_pos.push_back({1 , 1});
    string ans = "";
    for(int st = 1; st <= numrow + numcol - 1; ++st){
        assert(need_k > 0 && sz(cur_pos));
        ans += a[cur_pos[0].first][cur_pos[0].second];

        vector<pair<int,int>> v;

        for(auto& x : cur_pos){
            for(int t = 0; t < 2; ++t){
                int nxt_u = x.first + dx[t];
                int nxt_v = x.second + dy[t];
                if (nxt_u <= numrow && nxt_v <= numcol){
                    v.push_back({nxt_u , nxt_v});
                }
            }
        }

        sort(v.begin() , v.end() , [&](pair<int,int> x , pair<int,int> y){
            return a[x.first][x.second] < a[y.first][y.second];
        });
        pair<int,int> need_p;
        int t = -1;
        for(int i = 0; i < v.size(); ++i){
            if (ways(v[i].first , v[i].second) >= need_k){
                need_p = v[i];
                t = i;
                break;
            }
            need_k -= ways(v[i].first , v[i].second);
        }
        cur_pos.clear();
        for(int i = 0; i < v.size(); ++i) {
            if (a[need_p.first][need_p.second] == a[v[i].first][v[i].second]) {
                cur_pos.push_back(v[i]);
                if (i < t) need_k += ways(v[i].first , v[i].second);
            }
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 100