Submission #1036515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036515		model_code	Toy (CEOI24_toy)	C++17	35 / 100	1612 ms	776808 KiB

Main

// Author: Ondra Sladký
// State-based solution in O(w^2h^2).
// It should solve the first two subtasks.

#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<v<v<bool>>>> states;

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, int>> {
        {0, 1, 0},
        {0, -1, 0},
        {0, 0, 1},
        {0, 0, -1},
        {1, 1, 0},
        {1, -1, 0},
        {1, 0, 1},
        {1, 0, -1},
    };
    queue<tuple<int, int, int, int>> q;
    q.push({xhI, yhI, xvI, yvI});
    states = v<v<v<v<bool>>>>(w, v<v<v<bool>>>(h, v<v<bool>>(w, v<bool>(h, false))));
    states[xhI][yhI][xvI][yvI] = true;
    while (!q.empty()) {
        auto [xh, yh, xv, yv] = q.front();
        q.pop();
        for (auto [obj, dx, dy] : directions) {
            int nxh = xh + obj * dx;
            int nyh = yh + obj * dy;
            int nxv = xv + (!obj) * dx;
            int nyv = yv + (!obj) * dy;

            // Fast check for obstacles

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

            // Check if the objects overlap.
            int nddx = nxv - nxh;
            int nddy = nyh - nyv;
            if (nddx < 0 || nddx >= k || nddy < 0 || nddy >= l) blocked = true;

            if (blocked) continue;

            if (states[nxh][nyh][nxv][nyv]) continue;
            states[nxh][nyh][nxv][nyv] = true;
            q.push({nxh, nyh, nxv, nyv});
        }
    }


    bool reached = false;
    f(i, 0, w) f(j, 0, h) {
        if (states[i][yt][xt][j]) {
            reached = true;
            break;
        }
    }

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

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 0 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27