CSES - HIIT Open 2018

Submission details
Task:	Find a Word
Sender:	Karhukopla
Submission time:	2018-05-26 12:27:24 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.01 s	details
#2	ACCEPTED	0.01 s	details
#3	ACCEPTED	0.01 s	details
#4	ACCEPTED	0.02 s	details
#5	ACCEPTED	0.01 s	details
#6	ACCEPTED	0.01 s	details
#7	ACCEPTED	0.01 s	details
#8	ACCEPTED	0.01 s	details
#9	ACCEPTED	0.01 s	details
#10	ACCEPTED	0.01 s	details
#11	ACCEPTED	0.03 s	details
#12	ACCEPTED	0.03 s	details
#13	ACCEPTED	0.04 s	details
#14	ACCEPTED	0.02 s	details
#15	ACCEPTED	0.02 s	details
#16	ACCEPTED	0.02 s	details

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 () {
	ll 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;
}

/**
AAU
YBA
BTY
*/

Test details

Test 1

Verdict: ACCEPTED

input
`4 1 AAAA AAAA AAAA AAAA` view save

correct output
`AAAAAAA` view save

user output
`AAAAAAA` view save

Test 2

Verdict: ACCEPTED

input
`4 2 AAAA AAAA AAAA AAAA` view save

correct output
`AAAAAAA` view save

user output
`AAAAAAA` view save

Test 3

Verdict: ACCEPTED

input
`4 10 AAAA AAAA AAAA AAAA` view save

correct output
`AAAAAAA` view save

user output
`AAAAAAA` view save

Test 4

Verdict: ACCEPTED

input
`4 19 AAAA AAAA AAAA AAAA` view save

correct output
`AAAAAAA` view save

user output
`AAAAAAA` view save

Test 5

Verdict: ACCEPTED

input
`4 20 AAAA AAAA AAAA AAAA` view save

correct output
`AAAAAAA` view save

user output
`AAAAAAA` view save

Test 6

Verdict: ACCEPTED

input
`4 1 QNJP EVJU XHZF RXCV` view save

correct output
`QEVHXCV` view save

user output
`QEVHXCV` view save

Test 7

Verdict: ACCEPTED

input
`4 2 QNJP EVJU XHZF RXCV` view save

correct output
`QEVHZCV` view save

user output
`QEVHZCV` view save

Test 8

Verdict: ACCEPTED

input
`4 10 QNJP EVJU XHZF RXCV` view save

correct output
`QEXRXCV` view save

user output
`QEXRXCV` view save

Test 9

Verdict: ACCEPTED

input
`4 19 QNJP EVJU XHZF RXCV` view save

correct output
`QNVJZCV` view save

user output
`QNVJZCV` view save

Test 10

Verdict: ACCEPTED

input
`4 20 QNJP EVJU XHZF RXCV` view save

correct output
`QNVJZFV` view save

user output
`QNVJZFV` view save

Test 11

Verdict: ACCEPTED

input
`30 1 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ...` view save

correct output
`AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...` view save

user output
`AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...` view save

Test 12

Verdict: ACCEPTED

input
`30 15033633249770520 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ...` view save

correct output
`AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...` view save

user output
`AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...` view save

Test 13

Verdict: ACCEPTED

input
`30 30067266499541040 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ...` view save

correct output
`AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...` view save

user output
`AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...` view save

Test 14

Verdict: ACCEPTED

input
`30 1 QNJPEVJUXHZFRXCVKBSJKUURVPLYUI RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP WYLTEQJBJRPSEMPOESVKFTQKEMSIAP ...` view save

correct output
`QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...` view save

user output
`QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...` view save

Test 15

Verdict: ACCEPTED

input
`30 15033633249770520 QNJPEVJUXHZFRXCVKBSJKUURVPLYUI RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP WYLTEQJBJRPSEMPOESVKFTQKEMSIAP ...` view save

correct output
`QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...` view save

user output
`QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...` view save

Test 16

Verdict: ACCEPTED

input
`30 30067266499541040 QNJPEVJUXHZFRXCVKBSJKUURVPLYUI RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP WYLTEQJBJRPSEMPOESVKFTQKEMSIAP ...` view save

correct output
`QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...` view save

user output
`QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...` view save

HIIT Open 2018

Find a Word

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (Karhukopla)