QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #64515 | #4432. Jungle Trail | abdelrahman001# | WA | 622ms | 101916kb | C++20 | 7.1kb | 2022-11-24 22:47:13 | 2022-11-24 22:47:16 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int N = 2000 + 5, mod = 1e9 + 7;
int n, m, dp[N][N][2][3];
bool row[N], col[N];
string s[N], ans;
int getState(int i, int j) {
assert(s[i][j] != '#' && s[i][j] != '.');
return s[i][j] == '@';
}
int solve(int i, int j, bool row, int flip) {
if (i == n - 1 && j == m - 1) {
return 1;
}
auto &ret = dp[i][j][row][flip];
if (~ret) {
return ret;
}
ret = 0;
if (j + 1 < m) {
auto cur = s[i][j];
if (cur != '#') {
if (row) {
if (cur == '.' || !(flip ^ getState(i, j))) {
ret |= solve(i, j + 1, 1, flip);
}
} else {
if (cur == '.') {
ret |= solve(i, j + 1, 1, 0);
ret |= solve(i, j + 1, 1, 1);
} else {
ret |= solve(i, j + 1, 1, flip ^ getState(i, j));
}
}
}
}
if (i + 1 < n) {
auto cur = s[i][j];
if (cur != '#') {
if (!row) {
if (cur == '.' || !(flip ^ getState(i, j))) {
ret |= solve(i + 1, j, 0, flip);
}
} else {
if (cur == '.') {
ret |= solve(i + 1, j, 0, 0);
ret |= solve(i + 1, j, 0, 1);
} else {
ret |= solve(i + 1, j, 0, flip ^ getState(i, j));
}
}
}
}
return ret;
}
//void build(int i, int j, bool is_row, int state) {
// if (is_row) {
// if (state == 2) {
// row[i] = 'T';
// } else if (state == 1) {
// row[i] = 'N';
// }
// } else {
// if (state == 2) {
// col[j] = 'T';
// } else if (state == 1) {
// col[j] = 'N';
// }
// }
// if (i == n - 1 && j == m - 1) {
// return;
// }
// if (j + 1 < m) {
// auto nxt = s[i][j + 1];
// if (nxt != '#') {
// auto nxt_state = getState(i, j + 1);
// auto cur_lim = (is_row ? state : getState(i, j));
// auto can = nxt == '.' || !cur_lim || cur_lim == nxt_state;
// if (can) {
// if (solve(i, j + 1, 1, nxt_state != 0 ? nxt_state : (is_row ? state : getState(i, j)))) {
// ans += 'P';
// build(i, j + 1, 1,nxt_state != 0 ? nxt_state : (is_row ? state : getState(i, j)));
// return;
// }
// }
// }
// }
// ans += 'D';
// auto nxt_state = getState(i + 1, j);
// build(i + 1, j, 0, nxt_state != 0 ? nxt_state : (!is_row ? state : getState(i, j)));
//}
void build(int i, int j, bool is_row, int flip) {
if (i == n - 1 && j == m - 1) {
auto c = s[n - 1][m - 1];
if (c != '.') {
if (is_row) {
col[j] = flip ^ getState(i, j);
} else {
row[i] = flip ^ getState(i, j);
}
}
return;
}
if (j + 1 < m) {
auto cur = s[i][j];
if (cur != '#') {
if (is_row) {
if (cur == '.' || !(flip ^ getState(i, j))) {
if (solve(i, j + 1, 1, flip)) {
ans += 'P';
build(i, j + 1, 1, flip);
return;
}
}
} else {
if (cur == '.') {
if (solve(i, j + 1, 1, 0)) {
row[i] = 0;
ans += 'P';
build(i, j + 1, 1, 0);
return;
}
if (solve(i, j + 1, 1, 1)) {
row[i] = 1;
ans += 'P';
build(i, j + 1, 1, 1);
return;
}
} else {
if (solve(i, j + 1, 1, flip ^ getState(i, j))) {
row[i] = flip ^ getState(i, j);
ans += 'P';
build(i, j + 1, 1, flip ^ getState(i, j));
return;
}
}
}
}
}
if (i + 1 < n) {
auto cur = s[i][j];
if (cur != '#') {
if (!is_row) {
if (cur == '.' || !(flip ^ getState(i, j))) {
if (solve(i + 1, j, 0, flip)) {
ans += 'D';
build(i + 1, j, 0, flip);
return;
}
}
} else {
if (cur == '.') {
if (solve(i + 1, j, 0, 0)) {
col[j] = 0;
ans += 'D';
build(i + 1, j, 0, 0);
return;
}
if (solve(i + 1, j, 0, 1)) {
col[j] = 1;
ans += 'D';
build(i + 1, j, 0, 1);
return;
}
} else {
if (solve(i + 1, j, 0, flip ^ getState(i, j))) {
col[j] = flip ^ getState(i, j);
ans += 'D';
build(i + 1, j, 0, flip ^ getState(i, j));
return;
}
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string yes = "TAK", no = "NIE";
int tt;
cin >> tt;
while (tt--) {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
memset(dp, -1, n * sizeof (dp[0]));
memset(row, 0, sizeof (row));
memset(col, 0, sizeof (col));
ans.clear();
int x, y;
bool can = false;
for (x = 0; x < 2; ++x) {
for (y = 0; y < 2; ++y) {
if (solve(0, 0, x, y)) {
can = true;
break;
}
}
if (can) {
break;
}
}
// 1
// 4 5
// ..#..
// @@O@@
// ##@#O
// ..@.@
if (can) {
cout << yes << '\n';
if (x == 0) {
row[0] = y;
} else {
col[0] = y;
}
build(0, 0, x, y);
for (int i = 0; i < n; ++i) {
cout << (row[i] ? 'T' : 'N');
}
cout << '\n';
for (int i = 0; i < m; ++i) {
cout << (col[i] ? 'T' : 'N');
}
cout << '\n';
cout << ans << '\n';
} else {
cout << no << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 622ms
memory: 101916kb
input:
486 4 5 ..#.. @@O@@ ##@#O ..@.@ 2 2 OO OO 2 2 @@ @@ 2 2 @@ #@ 2 2 @O #@ 2 2 @@ OO 2 2 O# @O 2 2 @# #@ 2 2 @. .@ 2 2 @# .O 2 2 OO .O 10 10 @O@O#O@@@# OO#@#@@#OO #@#@#O##O@ OO##@@O#@O O##@@#@O#@ OO@OO@@@O@ @O#@#@O#@O @OOOOO@##. O@OOO##O@@ OO@@OOOO#@ 10 10 @@#OOO#O@@ #@@OO@@.O@ #.O@@O#@@O OO@@#O@#O@ .#...
output:
TAK NTNN NNTNT PDPDDPP TAK NN NN PD TAK TT NN PD TAK TT NN PD TAK TN NT PD TAK TN NN PD TAK NT NT DP NIE TAK TT NN PD TAK TN NN DP TAK NN NN PD NIE TAK TTNTNNNNNT NNNNNNNNTN PDPDDPDDPPPPPDPDDD TAK NNNTTTNTNN NNTNTNTNTN PPDDDPPDPDPDPDPDPD TAK NNNNTNNNNT NNNNNNTTTT PPDDDPPPPDPDPDPDDD NIE NIE NIE TAK T...
result:
wrong answer you didn't find a solution but jury did (test case 16)