QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497868#9164. ToyQwerty1232#0 5ms6264kbC++233.4kb2024-07-29 19:42:332024-07-29 19:42:34

Judging History

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

  • [2024-07-29 19:42:34]
  • 评测
  • 测评结果:0
  • 用时:5ms
  • 内存:6264kb
  • [2024-07-29 19:42:33]
  • 提交

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%