QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601950 | #9164. Toy | liuziao# | 0 | 8ms | 32308kb | C++23 | 3.3kb | 2024-09-30 16:36:23 | 2024-09-30 16:36:24 |
Judging History
answer
#include <bits/stdc++.h>
// #define int int64_t
const int kMaxN = 1.5e3 + 5, kMaxT = kMaxN * kMaxN;
int n, m, len1, len2, xh, yh, xv, yv, xt, yt;
int pre1[kMaxN][kMaxN], pre2[kMaxN][kMaxN], nxt1[kMaxN][kMaxN], nxt2[kMaxN][kMaxN];
int l1[kMaxN][kMaxN], r1[kMaxN][kMaxN], l2[kMaxN][kMaxN], r2[kMaxN][kMaxN], fa[kMaxT];
std::string s[kMaxN];
int getid(int x, int y) { return (x - 1) * m + y; }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void unionn(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) fa[fx] = fy;
}
void prework() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s[i][j] == 'X') {
pre1[i][j] = i, pre2[i][j] = j;
} else {
pre1[i][j] = pre1[i - 1][j];
pre2[i][j] = pre2[i][j - 1];
}
}
}
for (int i = n; i; --i) {
for (int j = m; j; --j) {
if (s[i][j] == 'X') {
nxt1[i][j] = i, nxt2[i][j] = j;
} else {
nxt1[i][j] = nxt1[i + 1][j];
nxt2[i][j] = nxt2[i][j + 1];
if (!nxt1[i][j]) nxt1[i][j] = n + 1;
if (!nxt2[i][j]) nxt2[i][j] = m + 1;
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
l1[i][j] = std::max(pre1[i][j] + 1, i - len1 + 1);
r1[i][j] = std::min(nxt1[i][j] - len1, i);
l2[i][j] = std::max(pre2[i][j] + 1, j - len2 + 1);
r2[i][j] = std::min(nxt2[i][j] - len2, j);
// if (l1[i][j] <= r1[i][j] && l2[i][j] <= r2[i][j]) {
// std::cerr << "??? " << i << ' ' << j << ' ' << l1[i][j] << ' ' << r1[i][j] << ' ' << l2[i][j] << ' ' << r2[i][j] << '\n';
// std::cerr << "!!! " << i << ' ' << j << ' ' << pre1[i][j] << ' ' << nxt1[i][j] << ' ' << pre2[i][j] << ' ' << nxt2[i][j] << '\n';
// }
}
}
}
void dickdreamer() {
std::cin >> n >> m >> len1 >> len2;
std::cin >> xh >> yh >> xv >> yv;
std::swap(n, m), std::swap(len1, len2), std::swap(xh, yh), std::swap(xv, yv);
++xh, ++yh, ++xv, ++yv;
for (int i = 1; i <= n; ++i) {
std::cin >> s[i];
s[i] = " " + s[i];
for (int j = 1; j <= m; ++j) {
if (s[i][j] == '*') {
xt = i, yt = j;
}
}
}
prework();
for (int i = 1; i <= n * m; ++i) fa[i] = i;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i < n) {
if (std::max(l1[i][j], l1[i][j + 1]) <= std::min(r1[i][j], r1[i][j + 1]) &&
std::max(l2[i][j], l2[i][j + 1]) <= std::min(r2[i][j], r2[i][j + 1])) {
unionn(getid(i, j), getid(i + 1, j));
}
}
if (j < m) {
if (std::max(l1[i][j], l1[i][j + 1]) <= std::min(r1[i][j], r1[i][j + 1]) &&
std::max(l2[i][j], l2[i][j + 1]) <= std::min(r2[i][j], r2[i][j + 1])) {
unionn(getid(i, j), getid(i, j + 1));
}
}
}
}
// std::cerr << xh << ' ' << yv << ' ' << xt << ' ' << yt << ' ' << find(getid(xh, yv)) << ' ' << find(getid(xt, yt)) << '\n';
std::cout << (find(getid(xh, yv)) == find(getid(xt, yt)) ? "YES\n" : "NO\n");
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int T = 1;
// std::cin >> T;
while (T--) dickdreamer();
// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\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: 12008kb
input:
32 16 23 15 3 8 4 1 ................................ ................................ ................................ ................................ ................................ *............................... ................................ ................................ ...................
output:
YES
result:
ok answer is YES
Test #2:
score: 14
Accepted
time: 0ms
memory: 16588kb
input:
50 50 22 14 26 34 36 33 .................................................. .................................................. .................................................. .................................................. .................................................. ........................
output:
YES
result:
ok answer is YES
Test #3:
score: 14
Accepted
time: 0ms
memory: 12696kb
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: 12816kb
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: 12624kb
input:
50 50 29 46 11 5 29 3 .................................................. .................................................. .................................................. .................................................. ....................X.......................X..... ..........................
output:
NO
result:
ok answer is NO
Test #6:
score: 14
Accepted
time: 3ms
memory: 16880kb
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: 2ms
memory: 12340kb
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: 14624kb
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: 2ms
memory: 12720kb
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: 16008kb
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: 22436kb
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: 18348kb
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: 14
Accepted
time: 0ms
memory: 16900kb
input:
48 50 24 21 3 9 6 3 ................................................ ................................................ ................................................ ................................................ ................................................ ......................................
output:
NO
result:
ok answer is NO
Test #14:
score: 14
Accepted
time: 0ms
memory: 16660kb
input:
50 45 23 25 0 27 14 12 .................................................. .................................................. .................................................. .................................................. .................................................. .........................
output:
NO
result:
ok answer is NO
Test #15:
score: 14
Accepted
time: 3ms
memory: 14680kb
input:
50 46 23 25 2 25 20 16 .................................................. .................................................. .................................................. .................................................. .................................................. .........................
output:
NO
result:
ok answer is NO
Test #16:
score: 14
Accepted
time: 0ms
memory: 12696kb
input:
50 50 25 25 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
NO
result:
ok answer is NO
Test #17:
score: 14
Accepted
time: 0ms
memory: 14972kb
input:
50 50 24 24 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
NO
result:
ok answer is NO
Test #18:
score: 14
Accepted
time: 0ms
memory: 16812kb
input:
50 50 23 23 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
NO
result:
ok answer is NO
Test #19:
score: 14
Accepted
time: 3ms
memory: 14908kb
input:
50 50 25 25 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
YES
result:
ok answer is YES
Test #20:
score: 14
Accepted
time: 0ms
memory: 12640kb
input:
50 50 24 24 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
YES
result:
ok answer is YES
Test #21:
score: 14
Accepted
time: 0ms
memory: 16556kb
input:
50 50 23 23 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
YES
result:
ok answer is YES
Test #22:
score: 14
Accepted
time: 0ms
memory: 12644kb
input:
50 50 12 12 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ ............................
output:
YES
result:
ok answer is YES
Test #23:
score: 14
Accepted
time: 3ms
memory: 12692kb
input:
50 50 11 11 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ ............................
output:
YES
result:
ok answer is YES
Test #24:
score: 14
Accepted
time: 0ms
memory: 14764kb
input:
50 50 12 12 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ ............................
output:
YES
result:
ok answer is YES
Test #25:
score: 14
Accepted
time: 0ms
memory: 12648kb
input:
50 50 11 11 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ ............................
output:
YES
result:
ok answer is YES
Test #26:
score: 14
Accepted
time: 3ms
memory: 14892kb
input:
50 50 10 10 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ ............................
output:
YES
result:
ok answer is YES
Test #27:
score: 14
Accepted
time: 0ms
memory: 16756kb
input:
50 50 9 9 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ .........................X....
output:
YES
result:
ok answer is YES
Test #28:
score: 14
Accepted
time: 3ms
memory: 14848kb
input:
50 47 8 8 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ..............................
output:
YES
result:
ok answer is YES
Test #29:
score: 0
Wrong Answer
time: 0ms
memory: 12612kb
input:
45 48 10 10 0 0 0 0 ............................................. ............................................. ............................................. ............................................. ............................................. ............................................. .......
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: 0ms
memory: 16688kb
input:
105 31 8 4 70 27 75 26 ......................................................................................................... ......................................................................................................... ....................................................................
output:
YES
result:
ok answer is YES
Test #90:
score: 9
Accepted
time: 0ms
memory: 30400kb
input:
300 300 4 8 231 246 234 240 ...................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #91:
score: 9
Accepted
time: 4ms
memory: 25732kb
input:
300 300 10 10 151 143 155 137 .................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #92:
score: 9
Accepted
time: 0ms
memory: 14936kb
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: 0ms
memory: 29276kb
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: 0ms
memory: 25796kb
input:
300 300 10 10 289 237 298 236 .........................................................................................X.......................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #95:
score: 9
Accepted
time: 0ms
memory: 21560kb
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: 5ms
memory: 31528kb
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: 0ms
memory: 27648kb
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: 0ms
memory: 26892kb
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: 8ms
memory: 32308kb
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: 0ms
memory: 30652kb
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: 9
Accepted
time: 0ms
memory: 31624kb
input:
286 296 9 9 19 286 26 279 .....................................................................................................................................................................................................................................................................................
output:
NO
result:
ok answer is NO
Test #102:
score: 9
Accepted
time: 4ms
memory: 25656kb
input:
284 284 9 9 36 50 40 42 .......................................................................................................................................................................................................................................................................................
output:
NO
result:
ok answer is NO
Test #103:
score: 9
Accepted
time: 0ms
memory: 25768kb
input:
270 299 10 9 35 258 39 253 .............................................................................................................................................................................................................................................................................. .....
output:
NO
result:
ok answer is NO
Test #104:
score: 9
Accepted
time: 4ms
memory: 26284kb
input:
300 300 10 10 0 0 0 0 .........................................................................................................................................................................................................................................................................................
output:
NO
result:
ok answer is NO
Test #105:
score: 9
Accepted
time: 0ms
memory: 25796kb
input:
300 300 9 9 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
output:
NO
result:
ok answer is NO
Test #106:
score: 9
Accepted
time: 3ms
memory: 30616kb
input:
300 300 8 8 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
output:
NO
result:
ok answer is NO
Test #107:
score: 9
Accepted
time: 5ms
memory: 29828kb
input:
300 300 10 10 0 0 0 0 .........................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #108:
score: 9
Accepted
time: 0ms
memory: 27272kb
input:
300 300 9 9 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #109:
score: 9
Accepted
time: 0ms
memory: 29396kb
input:
300 300 8 8 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #110:
score: 9
Accepted
time: 0ms
memory: 31612kb
input:
300 300 10 10 0 0 0 0 ......................................................................................................................................................X..................................................................................................................................
output:
YES
result:
ok answer is YES
Test #111:
score: 9
Accepted
time: 4ms
memory: 29108kb
input:
300 300 9 9 0 0 0 0 ......................................................................................................................................................X....................................................................................................................................
output:
YES
result:
ok answer is YES
Test #112:
score: 9
Accepted
time: 4ms
memory: 29192kb
input:
300 300 10 10 0 0 0 0 ......................................................................................................................................................X..................................................................................................................................
output:
YES
result:
ok answer is YES
Test #113:
score: 9
Accepted
time: 6ms
memory: 25724kb
input:
300 300 9 9 0 0 0 0 ......................................................................................................................................................X....................................................................................................................................
output:
YES
result:
ok answer is YES
Test #114:
score: 9
Accepted
time: 0ms
memory: 30024kb
input:
300 300 8 8 0 0 0 0 ......................................................................................................................................................X....................................................................................................................................
output:
YES
result:
ok answer is YES
Test #115:
score: 9
Accepted
time: 3ms
memory: 29548kb
input:
300 300 7 7 0 0 0 0 ......................................................................................................................................................X....................................................................................................................................
output:
YES
result:
ok answer is YES
Test #116:
score: 9
Accepted
time: 3ms
memory: 27344kb
input:
300 289 8 8 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #117:
score: 0
Wrong Answer
time: 0ms
memory: 31736kb
input:
285 293 5 5 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
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%