CSES - HIIT Open 2018 - Results
Submission details
Task:Find a Word
Sender:KnowYourArchitecture
Submission time:2018-05-26 14:23:37
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.01 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.01 sdetails
#13ACCEPTED0.01 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.01 sdetails

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;

string s[40];
ll ways[40][40];

char ans[1010];

pair<ll,ll> dbg[40][40];
ll mult[40][40];

int main() {
	int n;
	ll k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> s[i];
	ways[n-1][n-1] = 1;
	for (int i = n-1; i >= 0; i--) {
		for (int j = n-1; j >= 0; j--) {
			if (j == n-1 && i == n-1) continue;
			ways[i][j] = ways[i][j+1] + ways[i+1][j];
		}
	}
	
	map<pair<ll,ll>,set<pair<ll,pair<ll,ll>>>> old;
	old[{0,ways[0][0]}].emplace(1,pair<ll,ll>(0,0));--k;
	mult[0][0]=1;
	for (int diag = 0; diag < 2*n; diag++) {
		map<pair<ll,ll>,map<char,vector<pair<ll,pair<ll,ll>>>>> nw;
		for(auto& it: old){
			ll i,j;
			tie(i,j) = it.first;
			if(i>k || j<=k)continue;
			for(auto& jt : it.second){
				ll x,y,cnt;
				pair<ll,ll> coord;
				tie(cnt,coord) = jt;
				tie(x,y) = coord;
				dbg[x][y] = {i,j};
				ans[diag]=s[x][y];
				if(x+1<n)nw[{i,j}][s[x+1][y]].emplace_back(cnt,pair<ll,ll>(x+1,y));
				if(y+1<n)nw[{i,j}][s[x][y+1]].emplace_back(cnt,pair<ll,ll>(x,y+1));
			}
		}
		old.clear();
		for (auto& it : nw) {
			ll lasti;
			ll i,j;
			tie(i,j) = it.first;
			lasti=i;
			for(auto &jt:it.second){
				if(lasti>k)break;
				ll ni=lasti;
				for(auto& kt : jt.second){
					ll cnt,x,y;
					pair<ll,ll> coord;
					tie(cnt,coord) = kt;
					tie(x,y) = coord;
					ni+=ways[x][y]*cnt;
					mult[x][y]+=cnt;
				}
				if(ni>k){
					for(auto& kt : jt.second){
						ll cnt,x,y;
						pair<ll,ll> coord;
						tie(cnt,coord	) = kt;
						tie(x,y) = coord;
						old[{lasti,ni}].insert({mult[x][y],coord});
						dbg[x][y]={lasti,ni};
					}
					break;
				}
				lasti=ni;
			}
		}
	}
	//for(int i=0;i<n;++i){for(int j=0;j<n;++j)cout<<dbg[i][j].first<<','<<dbg[i][j].second<<' ';cout<<'\n';}
	//for(int i=0;i<n;++i){for(int j=0;j<n;++j)cout<<ways[i][j]<<' ';cout<<'\n';}
	cout<<ans<<endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
4 1
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

Test 2

Verdict: ACCEPTED

input
4 2
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

Test 3

Verdict: ACCEPTED

input
4 10
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

Test 4

Verdict: ACCEPTED

input
4 19
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

Test 5

Verdict: ACCEPTED

input
4 20
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

Test 6

Verdict: ACCEPTED

input
4 1
QNJP
EVJU
XHZF
RXCV

correct output
QEVHXCV

user output
QEVHXCV

Test 7

Verdict: ACCEPTED

input
4 2
QNJP
EVJU
XHZF
RXCV

correct output
QEVHZCV

user output
QEVHZCV

Test 8

Verdict: ACCEPTED

input
4 10
QNJP
EVJU
XHZF
RXCV

correct output
QEXRXCV

user output
QEXRXCV

Test 9

Verdict: ACCEPTED

input
4 19
QNJP
EVJU
XHZF
RXCV

correct output
QNVJZCV

user output
QNVJZCV

Test 10

Verdict: ACCEPTED

input
4 20
QNJP
EVJU
XHZF
RXCV

correct output
QNVJZFV

user output
QNVJZFV

Test 11

Verdict: ACCEPTED

input
30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

Test 12

Verdict: ACCEPTED

input
30 15033633249770520
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

Test 13

Verdict: ACCEPTED

input
30 30067266499541040
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

Test 14

Verdict: ACCEPTED

input
30 1
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...

user output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...

Test 15

Verdict: ACCEPTED

input
30 15033633249770520
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...

Test 16

Verdict: ACCEPTED

input
30 30067266499541040
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...