Submission #1279008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279008		SmuggingSpun	K-th path (IZhO11_kthpath)	C++20	100 / 100	1 ms	720 KiB

kthpath

#include<bits/stdc++.h>
#define taskname "D"
using namespace std;
typedef long long ll;
const int lim = 31;
int n, m;
char a[lim][lim];
ll Ckn[lim << 1][lim << 1];
string ans = "";
struct Data{
	int i, j;
	ll cnt;
	Data(){}
	Data(int i, int j, ll cnt){
		this->i = i;
		this->j = j;
		this->cnt = cnt;
	}
	bool operator <(const Data& other){
		return a[i][j] < a[other.i][other.j] || (a[i][j] == a[other.i][other.j] && make_pair(i, j) < make_pair(other.i, other.j));
	}
};
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	memset(Ckn, 0, sizeof(Ckn));
	for(int i = Ckn[0][0] = 1; i < (lim << 1); i++){
		for(int j = Ckn[0][i] = 1; j <= i; j++){
			Ckn[j][i] = Ckn[j][i - 1] + Ckn[j - 1][i - 1];
		} 
	}
	ll k;
	cin >> k;
	vector<Data>p(1, Data(1, 1, 1LL));
	for(int i = 0; i < n + m - 1; i++){
		sort(p.begin(), p.end());
		vector<Data>np;
		np.push_back(p[0]);
		for(int j = 1; j < p.size(); j++){
			if(p[j].i != np.back().i || p[j].j != np.back().j){
				np.push_back(p[j]);
			}
			else{
				np.back().cnt += p[j].cnt;
			}
		}
		swap(p, np);
		char z;
		vector<pair<char, ll>>rem;
		for(Data& it : p){
			int N = n - it.i + 1, M = m - it.j + 1;
			ll C = it.cnt * Ckn[N - 1][N + M - 2];
			if(C < k){
				k -= C;
				rem.push_back(make_pair(a[it.i][it.j], C));
			}
			else{
				ans += (z = a[it.i][it.j]);
				break;
			}
		}
		while(!rem.empty() && rem.back().first == z){
			k += rem.back().second;
			rem.pop_back();
		}
		np.clear();
		for(Data& it : p){
			if(a[it.i][it.j] == z){
				if(it.i < n){
					np.push_back(Data(it.i + 1, it.j, it.cnt));
				}
				if(it.j < m){
					np.push_back(Data(it.i, it.j + 1, it.cnt));
				}
			}
		}
		swap(p, np);
	}
	cout << ans;
}

Compilation message (stderr)

kthpath.cpp: In function 'int main()':
kthpath.cpp:26:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100