QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497868 | #9164. Toy | Qwerty1232# | 0 | 5ms | 6264kb | C++23 | 3.4kb | 2024-07-29 19:42:33 | 2024-07-29 19:42:34 |
answer
#include <bits/stdc++.h>
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::swap(n, m);
int K, L;
std::cin >> K >> L;
std::swap(K, L);
std::pair<int, int> ph, pv;
std::cin >> ph.first >> ph.second >> pv.first >> pv.second;
std::swap(ph.first, ph.second);
std::swap(pv.first, pv.second);
std::vector<std::string> input(n);
for (auto& s : input) {
std::cin >> s;
}
std::pair<int, int> tg;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (input[i][j] == '*') {
tg = {i, j};
}
}
}
std::vector<std::vector<int>> prf(n + 1, std::vector<int>(m + 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
prf[i + 1][j + 1] = (input[i][j] == 'X') + prf[i][j + 1] + prf[i + 1][j] - prf[i][j];
}
}
auto get_sum = [&](char tp, std::pair<int, int> p) {
std::pair<int, int> p2(p.first + (tp == 'h' ? 1 : K), p.second + (tp == 'h' ? L : 1));
if (p.first < 0 || p.second < 0 || n < p2.first || m < p2.second) {
return 1;
}
int res = prf[p2.first][p2.second] - prf[p.first][p2.second] - prf[p2.first][p.second] + prf[p.first][p.second];
return res;
};
auto check_tg = [&](char tp, std::pair<int, int> p) {
std::pair<int, int> p2(p.first + (tp == 'h' ? 1 : K), p.second + (tp == 'h' ? L : 1));
if (p.first < 0 || p.second < 0 || n < p2.first || m < p2.second) {
return false;
}
return p.first <= tg.first && tg.first < p2.first && p.second <= tg.second && tg.second < p2.second;
};
std::vector<int> rv(n * m), rh(n * m);
for (char ch : std::string{"vh"}) {
auto& vec = ch == 'h' ? rh : rv;
std::vector<int> stack;
stack.push_back((ch == 'h') ? ph.first * m + ph.second : pv.first * m + pv.second);
while (stack.size()) {
int v = stack.back();
stack.pop_back();
if (!vec[v]) {
vec[v] = 1;
auto [x, y] = div(v, m);
assert(get_sum(ch, {x, y}) == 0);
for (auto [dx, dy] : std::array<std::pair<int, int>, 4>{{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}}) {
int x2 = x + dx, y2 = y + dy;
if (get_sum(ch, {x2, y2}) == 0) {
stack.push_back(x2 * m + y2);
}
}
}
}
}
// for (auto vec : std::vector{rv, rh}) {
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// if (vec[i * m + j]) {
// std::cerr << "+";
// } else {
// std::cerr << input[i][j];
// }
// }
// std::cerr << std::endl;
// }
// std::cerr << std::endl;
// }
bool suc1 = false, suc2 = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
suc1 |= rv[i * m + j] && check_tg('v', {i, j});
suc2 |= rh[i * m + j] && check_tg('h', {i, j});
}
}
if (suc1 && suc2) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 14
Accepted
time: 0ms
memory: 3580kb
input:
32 16 23 15 3 8 4 1 ................................ ................................ ................................ ................................ ................................ *............................... ................................ ................................ ...................
output:
YES
result:
ok answer is YES
Test #2:
score: 14
Accepted
time: 0ms
memory: 3628kb
input:
50 50 22 14 26 34 36 33 .................................................. .................................................. .................................................. .................................................. .................................................. ........................
output:
YES
result:
ok answer is YES
Test #3:
score: 14
Accepted
time: 0ms
memory: 3604kb
input:
50 50 50 50 0 18 2 0 .................................................. ...............................................X.. .................................................. .................................................. .................................................. ...........................
output:
NO
result:
ok answer is NO
Test #4:
score: 14
Accepted
time: 0ms
memory: 3564kb
input:
5 47 4 47 1 25 3 0 .X... ..... ..... .X... ..... ..... ..... ..... ..... ..... ..... ..... ..*.. ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... X.... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .....
output:
YES
result:
ok answer is YES
Test #5:
score: 14
Accepted
time: 0ms
memory: 3832kb
input:
50 50 29 46 11 5 29 3 .................................................. .................................................. .................................................. .................................................. ....................X.......................X..... ..........................
output:
NO
result:
ok answer is NO
Test #6:
score: 14
Accepted
time: 0ms
memory: 3656kb
input:
50 50 50 50 0 37 22 0 ............X.............X..............X........ .................................................. .................................................. ....................................X............. ................................X................. ....................X.....
output:
NO
result:
ok answer is NO
Test #7:
score: 14
Accepted
time: 1ms
memory: 3640kb
input:
27 34 19 18 5 29 20 14 ............X..X.X.X..XX..X .....X..X...XX............. .......X.X........X........ X...................X...X.. ....XX..................... .................X........X ..........X.X.....X.......X ..........X......X....X.... X..X........XX.....X....... ..X.X............X..........
output:
NO
result:
ok answer is NO
Test #8:
score: 14
Accepted
time: 0ms
memory: 3888kb
input:
50 50 16 16 21 35 36 33 .X.............XX....X...X.......X................ .................X.......X.........X........X..... ...X........X......XX........X.......X...........X .X......X.......X.....X.X................X.XX....X ......X.........................X.............X.X. ........X...X..X...X....
output:
NO
result:
ok answer is NO
Test #9:
score: 14
Accepted
time: 0ms
memory: 3600kb
input:
50 50 50 50 0 20 3 0 .......X.......................................... ....X............X.......X.......X...........X.... .......X....X........X..X.......X..........X..X... .X......X.......X.................X.............X. .................X.X....X..XX..................... .......X...................
output:
NO
result:
ok answer is NO
Test #10:
score: 14
Accepted
time: 0ms
memory: 3560kb
input:
4 7 4 5 0 2 0 1 .X.. .X.. .... ..X. ..X. .XX* XXXX
output:
NO
result:
ok answer is NO
Test #11:
score: 14
Accepted
time: 0ms
memory: 3656kb
input:
50 50 13 13 2 46 11 36 .X.X.X.....XX.XX.X..XX..XXXXXXX.XXX...XX.X.X.XXXX. .X..X...X.X.X.X.X.X..XX..XX.XXXX..X.X..XXX...X..X. X..X...X....XX....XX......X...X..XXX.X.X..X.X..... ...X.XX...X..XX.X..XX.X...X.X...X.XXX.XX..XX..XX.. ..X.XX...X.X.X..X.X.......X.X......X..X..X...X.X.X ......XX......X..X..X....
output:
NO
result:
ok answer is NO
Test #12:
score: 14
Accepted
time: 0ms
memory: 3596kb
input:
50 50 50 50 0 46 6 0 XX.....X....X...X.X.X..XX..XX...X.XX..X.......X... XXX........X.X.X.XX..X..XX..XXX....X.XX.....X...XX ..X.X...X.X.........X..X....XX....X*XXXXXXX...XX.. ....X..XX....X.X.X..X..XXX...XXX..XXX.X..X.XX.XXXX XXX......X.X.....X.X.........XXXXX.XX..X.X.X.XXX.X .X.....XXXX....X...X.XXX...
output:
NO
result:
ok answer is NO
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 3656kb
input:
48 50 24 21 3 9 6 3 ................................................ ................................................ ................................................ ................................................ ................................................ ......................................
output:
YES
result:
wrong answer expected NO, found YES
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #89:
score: 9
Accepted
time: 1ms
memory: 3784kb
input:
105 31 8 4 70 27 75 26 ......................................................................................................... ......................................................................................................... ....................................................................
output:
YES
result:
ok answer is YES
Test #90:
score: 9
Accepted
time: 2ms
memory: 5272kb
input:
300 300 4 8 231 246 234 240 ...................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #91:
score: 9
Accepted
time: 5ms
memory: 5212kb
input:
300 300 10 10 151 143 155 137 .................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #92:
score: 9
Accepted
time: 1ms
memory: 3816kb
input:
159 68 6 2 95 54 98 54 .........................................................................X..................................................................................... ..........................X..................................................X..........................................
output:
YES
result:
ok answer is YES
Test #93:
score: 9
Accepted
time: 2ms
memory: 5156kb
input:
300 300 10 10 11 147 12 143 .....................................................................X.................X.......................................*X..............................................X...................................................................................................
output:
YES
result:
ok answer is YES
Test #94:
score: 9
Accepted
time: 5ms
memory: 5108kb
input:
300 300 10 10 289 237 298 236 .........................................................................................X.......................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #95:
score: 9
Accepted
time: 1ms
memory: 3920kb
input:
277 111 6 9 109 9 112 5 ...................X..XX...........X.......X..................X...X.......X........X......X...........X....................X.......................X..X..X.........XX...................X..............X..........X..................X................X...................X............
output:
NO
result:
ok answer is NO
Test #96:
score: 9
Accepted
time: 2ms
memory: 4764kb
input:
300 300 6 6 126 5 131 1 .......X............XX..............X...X....XX..........X..X........X.X...X...........X.................X...............X..............X.....XX.............X....................................XX....X................X........X...................X.....X..........................
output:
NO
result:
ok answer is NO
Test #97:
score: 9
Accepted
time: 1ms
memory: 4584kb
input:
300 300 10 10 30 92 34 92 ...X..........X.........................X....................XX........XX......X..X.......X..................X..X...X..X.........X..................X.........X...........................XX................X....XX.......................X...........X..............................
output:
NO
result:
ok answer is NO
Test #98:
score: 9
Accepted
time: 1ms
memory: 4032kb
input:
121 248 8 4 20 157 23 156 ...XXX.....XX..XXXX...XX.XXX....X..XXX....XX.XX..X..XX.X...X...X.X............X....X...XXX..XX..X..X....X.X..X..X.....XXX ...XX..XX.XX..XX..XX..X...X..X..X.......X.X..X.XX......X....XX.X..X..X.X.X...X..XXX.XXXX...XXXX..X..X...X.XX........X.X.X XXXXX....X.X.X..XXXX.XX..XX.XX...
output:
NO
result:
ok answer is NO
Test #99:
score: 9
Accepted
time: 1ms
memory: 4532kb
input:
300 300 9 5 55 124 55 121 XX.X...X..X.X..X.....X..X..X.X.X...XX.XXX...XXX........XXX.........X..XX..X.X......X....XXXXX.X.X.X.X......X..X.X...XXXX..X....X.XXXX....XX..XX.X......XX.XX..X.....X.X.X.XXXX.X.XX.XXX....XX.X..X.X.XX.X.X...XX.X.X.XX...X.....X..XXX..X.XX...XXX...X.XXX...XX..X....XX.XXX.X.XXX...
output:
NO
result:
ok answer is NO
Test #100:
score: 9
Accepted
time: 1ms
memory: 4460kb
input:
300 300 10 10 94 163 96 156 X..X.....X..XXX.X.XXXXX..XXX..X....X..XX..XXX...XXX....X.XXXXX...XX...XX.X...XX.X...XX..XX...X.X...X.X.XX...XX..X..X.....X.X........X.XXX...XXX.XX....X.X.X....X......XXX.XX.XX..XXXX...XX....X.X.X.X...XXX.......XX..X..XX.....X...XX..X...XX.....XXX.XXXXX..X.X...X...X.XX..X....
output:
NO
result:
ok answer is NO
Test #101:
score: 0
Wrong Answer
time: 5ms
memory: 6264kb
input:
286 296 9 9 19 286 26 279 .....................................................................................................................................................................................................................................................................................
output:
YES
result:
wrong answer expected NO, found YES
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%