CSES - HIIT Open 2018 - Results
Submission details
Task:Find a Word
Sender:Karhukopla
Submission time:2018-05-26 12:19:40
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.02 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.01 sdetails
#11ACCEPTED0.03 sdetails
#120.04 sdetails
#130.04 sdetails
#14ACCEPTED0.02 sdetails
#150.04 sdetails
#160.04 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:24:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ans.length() != 2 * n - 1) ans.push_back('Z');
         ~~~~~~~~~~~~~^~~~~~~~~~~~

Code

#include <bits/stdc++.h>

#define ll long long
#define lll __int128
#define pii pair<int, int>
#define M 1000000007
#define N 30
using namespace std;

lll dp[N][N];
lll eq[N][N];
char c[N][N];

int main () {
	int n, kk;
	cin>>n>>kk;
	lll k = kk;
	string ans;
	
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) cin>>c[y][x];
	}
	
	while (ans.length() != 2 * n - 1) ans.push_back('Z');
	for (int i = 0; i < 2 * n - 1; i++) {
		bool b = true;
		while (b) {
			for (int y = 0; y < n; y++) {
				for (int x = 0; x < n; x++) eq[y][x] = dp[y][x] = 0;
			}
			for (int y = 0; y < n; y++) {
				for (int x = 0; x < n; x++) {
					int p = y + x;
					if (c[y][x] < ans[p]) {
						if (p == 0) {
							dp[y][x] = 1;
							eq[y][x] = 0;
						} else if (!y) {
							dp[y][x] = dp[y][x - 1] + eq[y][x - 1];
							eq[y][x] = 0;
						} else if (!x) {
							dp[y][x] = dp[y - 1][x] + eq[y - 1][x];
							eq[y][x] = 0;
						} else {
							dp[y][x] = dp[y - 1][x] + dp[y][x - 1] + eq[y - 1][x] + eq[y][x - 1];
							eq[y][x] = 0;
						}
					} else if (c[y][x] == ans[p]) {
						if (p == 0) {
							dp[y][x] = 0;
							eq[y][x] = 1;
						} else if (!y) {
							dp[y][x] = dp[y][x - 1];
							eq[y][x] = eq[y][x - 1];
						} else if (!x) {
							dp[y][x] = dp[y - 1][x];
							eq[y][x] = eq[y - 1][x];
						} else {
							dp[y][x] = dp[y - 1][x] + dp[y][x - 1];
							eq[y][x] = eq[y - 1][x] + eq[y][x - 1];
						}
					} else if (c[y][x] > ans[p]) {
						if (p == 0) {
							dp[y][x] = 0;
							eq[y][x] = 0;
						} else if (!y) {
							dp[y][x] = dp[y][x - 1];
							eq[y][x] = 0;
						} else if (!x) {
							dp[y][x] = dp[y - 1][x];
							eq[y][x] = 0;
						} else {
							dp[y][x] = dp[y - 1][x] + dp[y][x - 1];
							eq[y][x] = 0;
						}
					}
				}
			}
			if (dp[n - 1][n - 1] + eq[n - 1][n - 1] >= k) ans[i]--;
			else break;
		}
		ans[i]++;
	}
	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:

input
30 15033633249770520
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
...

Test 13

Verdict:

input
30 30067266499541040
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
...

Test 14

Verdict: ACCEPTED

input
30 1
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...

user output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...

Test 15

Verdict:

input
30 15033633249770520
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
...

Test 16

Verdict:

input
30 30067266499541040
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
...