Submission #1208148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208148		NK_	Toy (CEOI24_toy)	C++20	44 / 100	1186 ms	617300 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back

using str = string;
template<class T> using V = vector<T>;
// template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
using vs = V<str>;
using vi = V<int>;

const int nax = 305, wax = 90;
bitset<wax * wax> pos[nax][nax];
int hor[nax][nax], ver[nax][nax];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	memset(hor, 0, sizeof hor);
	memset(ver, 0, sizeof ver);

	int R, C, W, L; cin >> C >> R >> W >> L;

	int xw, yw, xl, yl; cin >> xw >> yw >> xl >> yl; 
	// --xw, --yw, --xl, --yl;

	vs A(R); for(auto& x : A) cin >> x;

	int er, ec; for(int r = 0; r < R; r++) for(int c = 0; c < C; c++) {
		if (A[r][c] == '*') {
			er = r, ec = c;
			A[r][c] = '.';
		}
	}

	for(int i = 0; i < R; i++) for(int j = 0; j < C; j++) {
		pos[i][j].reset();
	}	

	for(int i = 0; i < R; i++) {
		for(int j = C - 1; j >= 0; j--) {
			if (j + 1 < C) hor[i][j] = hor[i][j + 1];
			if (A[i][j] == '.') hor[i][j]++;
			if (A[i][j] == 'X') hor[i][j] = 0;
			// cout << hor[i][j] << " ";
		}
		// cout << endl;
	}

	for(int j = 0; j < C; j++) {
		for(int i = R - 1; i >= 0; i--) {
			if (i + 1 < R) ver[i][j] = ver[i + 1][j];
			if (A[i][j] == '.') ver[i][j]++;
			if (A[i][j] == 'X') ver[i][j] = 0;
			// cout << ver[i][j] << " ";
		}	
		// cout << endl;
	}	

	bool ans = 0;
	V<array<int, 4>> q; q.pb({yl, xw, yw - yl, xl - xw});
	while(sz(q)) {
		int r = q.back()[0];
		int c = q.back()[1];
		int rx = q.back()[2];
		int cx = q.back()[3];

		q.pop_back();

		// cout << r << " " << c << " " << rx << " " << cx << endl;
		pos[r][c][rx * wax + cx] = 1;

		int rw = r + rx, cw = c, rl = r, cl = c + cx;
		// cout << rw << " " << cw << " | " << rl << " " << cl << endl;
		if (rw == er && cl == ec) {
			ans = 1;
			break;
		}

		// move vertical left
		if (cl - 1 >= 0 && cx - 1 >= 0 && ver[rl][cl - 1] >= L) {
			if (!pos[r][c][rx * wax + cx - 1]) q.pb({r, c, rx, cx - 1});
		}

		// move vertical right
		if (cl + 1 < C && cx + 1 < W && ver[rl][cl + 1] >= L) {
			if (!pos[r][c][rx * wax + cx + 1]) q.pb({r, c, rx, cx + 1});
		}

		// move vertical up
		if (rl - 1 >= 0 && rx + 1 < L && ver[rl - 1][cl] >= L) {
			if (!pos[r - 1][c][(rx + 1) * wax + cx]) q.pb({r - 1, c, rx + 1, cx});
		}

		// move vertical down
		if (rl + 1 < R && rx - 1 >= 0 && ver[rl + 1][cl] >= L) {
			if (!pos[r + 1][c][(rx - 1) * wax + cx]) q.pb({r + 1, c, rx - 1, cx});
		}

		// move horizontal up
		if (rw - 1 >= 0 && rx - 1 >= 0 && hor[rw - 1][cw] >= W) {
			if (!pos[r][c][(rx - 1) * wax + cx]) q.pb({r, c, rx - 1, cx});
		}

		// move horizontal down
		if (rw + 1 < R && rx + 1 < L && hor[rw + 1][cw] >= W) {
			if (!pos[r][c][(rx + 1) * wax + cx]) q.pb({r, c, rx + 1, cx});
		}

		// move horizontal left
		if (cw - 1 >= 0 && cx + 1 < W && hor[rw][cw - 1] >= W) {
			if (!pos[r][c - 1][rx * wax + cx + 1]) q.pb({r, c - 1, rx, cx + 1});
		}

		// move horizontal right
		if (cw + 1 < C && cx - 1 >= 0 && hor[rw][cw + 1] >= W) {
			if (!pos[r][c + 1][rx * wax + cx - 1]) q.pb({r, c + 1, rx, cx - 1});
		}
	}

	cout << (ans ? "YES" : "NO") << nl;

	exit(0-0);
}

// Breathe In, Breathe Out

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