Submission #1286572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286572		_rain_	K-th path (IZhO11_kthpath)	C++20	0 / 100	380 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] , cnt[26] = {};
char a[N + 2][N + 2];

vector<pair<int,int>> pos[26] = {};
void reset(){
    for(int i = 0; i < 26; ++i) pos[i].clear();
    for(int i = 0; i < 26; ++i) cnt[i] = 0;
    return;
}
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){
        for(int j = 1; j <= numcol; ++j) cin >> a[i][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});
    for(int i = 1; i <= numrow + numcol - 1; ++i){
        assert(need_k > 0 && sz(cur_pos));
        cout << a[cur_pos[0].first][cur_pos[0].second] ;
        reset();

        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){
                    pos[a[nxt_u][nxt_v] - 'a'].push_back({nxt_u , nxt_v});
                    cnt[a[nxt_u][nxt_v] - 'a'] += ways(nxt_u , nxt_v);
                }
            }
        }

        for(int i = 0; i < 26; ++i){
            if (need_k <= cnt[i]){
                cur_pos = pos[i];
                break;
            }
            else need_k -= cnt[i];
        }
    }
    
    return 0;
}

• Subtask 1: 0 / 100