oj.uz

Submission #1036518

# Submission time Handle Problem Language Result Execution time Memory
1036518 2024-07-27T13:28:50 Z model_code Toy (CEOI24_toy) C++17
0 / 100
 5 ms 600 KB 
// Author: Ondra Sladký
// Incorrect solution which treats the two blocks as independent.
// It should receive 0 points.

#include <bits/stdc++.h>
using namespace std;
#define f(i, a, b) for (int i = (a); i < (b); i++)

#define v vector

int w, h, k, l;
int xhI, yhI, xvI, yvI;
int xt, yt;
v<v<bool>> grid;

v<v<bool>> validH;
v<v<bool>> validV;

v<v<bool>> statesH;
v<v<bool>> statesV;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> w >> h >> k >> l;
    cin >> xhI >> yhI >> xvI >> yvI;
    grid = v<v<bool>>(w, v<bool>(h));
    f(i, 0, h) {
        string s;
        cin >> s;
        f(j, 0, w) {
            char x = s[j];
            grid[j][i] = x == 'X';
            if (x == '*') {
                xt = j;
                yt = i;
            }
        }
    }

    // Precompute valid positions for horizontal and vertical blocks.
    validH = v<v<bool>>(w, v<bool>(h, false));
    validV = v<v<bool>>(w, v<bool>(h, false));

    f(i,0,h) {
        int last = -1;
        f(j,0,w) {
            if (grid[j][i]) {
                last = j;
            }
            int start = j - k + 1;
            if (start > last) {
                validH[start][i] = true;
            }
        }
    }

    f(i,0,w) {
        int last = -1;
        f(j,0,h) {
            if (grid[i][j]) {
                last = j;
            }
            int start = j - l + 1;
            if (start > last) {
                validV[i][start] = true;
            }
        }
    }


    auto directions = v<tuple<int, int>> {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    };
    queue<tuple<int, int>> q;
    q.push({xhI, yhI});
    statesH = v<v<bool>>(w, v<bool>(h, false));
    statesH[xhI][yhI] = true;
    while (!q.empty()) {
        auto [xh, yh] = q.front();
        q.pop();
        for (auto [dx, dy] : directions) {
            int nxh = xh + dx;
            int nyh = yh + dy;

            // Fast check for obstacles

            bool blocked = false;
            if (nxh < 0 || nxh >= w || nyh < 0 || nyh >= h) blocked = true;
            if (blocked) continue;
            if (!validH[nxh][nyh]) blocked = true;
            if (blocked) continue;

            if (statesH[nxh][nyh]) continue;
            statesH[nxh][nyh] = true;
            q.push({nxh, nyh});
        }
    }
    f(i,0,h) {
        int last = -k;
        f(j,0,w) {
            if (statesH[j][i]) {
                last = j;
            }
            statesH[j][i] = j - k < last;
        }
    }

    q.push({xvI, yvI});
    statesV = v<v<bool>>(w, v<bool>(h, false));
    statesV[xvI][yvI] = true;
    while (!q.empty()) {
        auto [xv, yv] = q.front();
        q.pop();
        for (auto [dx, dy] : directions) {
            int nxv = xv + dx;
            int nyv = yv + dy;

            // Fast check for obstacles

            bool blocked = false;
            if (nxv < 0 || nxv >= w || nyv < 0 || nyv >= h) blocked = true;
            if (blocked) continue;
            if (!validV[nxv][nyv]) blocked = true;
            if (blocked) continue;

            if (statesV[nxv][nyv]) continue;
            statesV[nxv][nyv] = true;
            q.push({nxv, nyv});
        }
    }
    f(i,0,w) {
        int last = -l;
        f(j,0,h) {
            if (statesV[i][j]) {
                last = j;
            }
            statesV[i][j] = j - l < last;
        }
    }


    bool reached = statesH[xt][yt] && statesV[xt][yt];

    cout << (reached ? "YES" : "NO") << endl;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 600 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 600 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 568 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 3 ms 564 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 600 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 600 KB Output isn't correct
16 Halted 0 ms 0 KB -