| Task: | Find a Word |
| Sender: | Karhukopla |
| Submission time: | 2018-05-26 12:19:40 +0300 |
| Language: | C++ |
| Status: | READY |
| Result: | WRONG ANSWER |
| 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 | WRONG ANSWER | 0.04 s | details |
| #13 | WRONG ANSWER | 0.04 s | details |
| #14 | ACCEPTED | 0.02 s | details |
| #15 | WRONG ANSWER | 0.04 s | details |
| #16 | WRONG ANSWER | 0.04 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 () {
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: WRONG ANSWER
| input |
|---|
| 30 15033633249770520 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ... |
| correct output |
|---|
| AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |
| user output |
|---|
| ... |
Test 13
Verdict: WRONG ANSWER
| 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: WRONG ANSWER
| input |
|---|
| 30 15033633249770520 QNJPEVJUXHZFRXCVKBSJKUURVPLYUI RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP WYLTEQJBJRPSEMPOESVKFTQKEMSIAP ... |
| correct output |
|---|
| QNXZYLYURTAYRYZQUKZCYOPKYKLQPX... |
| user output |
|---|
| ... |
Test 16
Verdict: WRONG ANSWER
| input |
|---|
| 30 30067266499541040 QNJPEVJUXHZFRXCVKBSJKUURVPLYUI RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP WYLTEQJBJRPSEMPOESVKFTQKEMSIAP ... |
| correct output |
|---|
| QRXZYLYURTAYRYZQUKZCYOPKYKLQPX... |
| user output |
|---|
| ... |