Submission #1036518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036518		model_code	Toy (CEOI24_toy)	C++17	0 / 100	5 ms	600 KiB

Main

// 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
• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27