QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#601950#9164. Toyliuziao#0 8ms32308kbC++233.3kb2024-09-30 16:36:232024-09-30 16:36:24

Judging History

你现在查看的是最新测评结果

  • [2024-09-30 16:36:24]
  • 评测
  • 测评结果:0
  • 用时:8ms
  • 内存:32308kb
  • [2024-09-30 16:36:23]
  • 提交

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;
}

详细

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%