Submission #1075531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075531		ProtonDecay314	Toy (CEOI24_toy)	C++17	44 / 100	1565 ms	213072 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef set<ll> sll;
#define IOS cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false)
#define INF(dtype) numeric_limits<dtype>::max()
#define NINF(dtype) numeric_limits<dtype>::min()
#define fi first
#define se second
#define pb push_back

typedef vector<vb> vvb;
typedef vector<vvb> v3b;
typedef vector<v3b> v4b;
typedef vector<string> vs;

struct bfs_state {
    int x, y, dx, dy;
};

bfs_state to_bfs_state(int xh, int yh, int xv, int yv, int k, int l) {
    int x = xv, y = yh;
    int dx = xh + k - 1 - x; // ! TODO recheck
    int dy = yv + l - 1 - y;

    return {x, y, dx, dy};
}

bool is_valid_state(bfs_state s, int k, int l, int w, int h) {
    int ex = s.x + s.dx;
    int sx = ex - k + 1;

    int ey = s.y + s.dy;
    int sy = ey - l + 1;

    return !(s.dx >= k || s.dx < 0 || s.dy >= l || s.dy < 0 || sx < 0 || ex >= w || sy < 0 || ey >= h);
}

int pos_type(bfs_state s, int k, int l, int w, int h, const vs& g) {
    int ex = s.x + s.dx;
    int sx = ex - k + 1;

    int ey = s.y + s.dy;
    int sy = ey - l + 1;

    if(!is_valid_state(s, k, l, w, h)) {
        // Invalid bfs states
        return 0;
    }

    for(int x = sx ; x <= ex; x++) {
        if(g[s.y][x] == 'X') {
            return 0;
        }
    }

    for(int y = sy ; y <= ey; y++) {
        if(g[y][s.x] == 'X') {
            return 0;
        }
    }

    return (g[s.y][s.x] == '*' ? 2 : 1);
}

bool solve(int w, int h, int k, int l, bfs_state s, const vs& g) {
    v4b vis;
    for(int i1 = 0; i1 < w; i1++) {
        v3b visr1;
        for(int i2 = 0; i2 < h; i2++) {
            vvb visr2;
            for(int i3 = 0; i3 < k; i3++) {
                vb visr3(l, false);
                visr2.pb(visr3);
            }
            visr1.pb(visr2);
        }
        vis.pb(visr1);
    }

    queue<bfs_state> q;

    q.push(s);

    while(!q.empty()) {
        // cout << "Anya likes peanuts" << endl;
        bfs_state cs = q.front();

        q.pop();

        if(!is_valid_state(cs, k, l, w, h)) continue;
        // cout << cs.x << " " << cs.y << " " << cs.dx << " " << cs.dy << endl;
        if(vis[cs.x][cs.y][cs.dx][cs.dy]) continue;
        vis[cs.x][cs.y][cs.dx][cs.dy] = true;

        int cptype = pos_type(cs, k, l, w, h, g);
        // cout << "Segfault lmao" << endl;
        if(cptype == 0) continue;
        if(cptype == 2) return true;

        // Enqueue through all possible next states
        // Move horiz left
        q.push({cs.x, cs.y, cs.dx - 1, cs.dy});

        // Move horiz right
        q.push({cs.x, cs.y, cs.dx + 1, cs.dy});

        // Move horiz up
        q.push({cs.x, cs.y + 1, cs.dx, cs.dy - 1});
        
        // Move horiz down
        q.push({cs.x, cs.y - 1, cs.dx, cs.dy + 1});

        // Move vert left
        q.push({cs.x - 1, cs.y, cs.dx + 1, cs.dy});

        // Move vert right
        q.push({cs.x + 1, cs.y, cs.dx - 1, cs.dy});

        // Move vert up
        q.push({cs.x, cs.y, cs.dx, cs.dy + 1});
        
        // Move vert down
        q.push({cs.x, cs.y, cs.dx, cs.dy - 1});
    }

    return false;
}

int main() {
    int w, h, k, l;
    cin >> w >> h >> k >> l;

    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;

    vs g(h);

    for(string& gv : g) cin >> gv;

    cout << (solve(w, h, k, l, to_bfs_state(xh, yh, xv, yv, k, l), g) ? "YES" : "NO") << endl;

    return 0;
}

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