Submission #1077112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077112		pawned	Toy (CEOI24_toy)	C++17	35 / 100	1104 ms	1048576 KiB

Main

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}


int dir1[8] = {-1, 1, 0, 0, 0, 0, 0, 0};
int dir2[8] = {0, 0, -1, 1, 0, 0, 0, 0};
int dir3[8] = {0, 0, 0, 0, -1, 1, 0, 0};
int dir4[8] = {0, 0, 0, 0, 0, 0, -1, 1};

int main() {
	fastIO();
	int R, C, K, L;
	// K = horizontal width, L = vertical width
	cin>>C>>R>>K>>L;
	pair<ii, ii> start;
	// {horizontal left coords, vertical top coords}
	cin>>start.fi.se>>start.fi.fi>>start.se.se>>start.se.fi;
	ii goal;	// goal cell
	vector<vector<char>> grid(R, vector<char>(C, '.'));
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin>>grid[i][j];
			if (grid[i][j] == '*')
				goal = {i, j};
		}
	}
	// prefix sums to check for filled
	vector<vi> pfs1(R, vi(C + 1, 0));	// horizontal prefix sums
	vector<vi> pfs2(R + 1, vi(C, 0));	// vertical prefix sums
	for (int i = 0; i < R; i++) {
		for (int j = 1; j <= C; j++) {
			pfs1[i][j] = pfs1[i][j - 1];
			if (grid[i][j - 1] == 'X')
				pfs1[i][j]++;
		}
	}
	for (int i = 0; i < C; i++) {
		for (int j = 1; j <= R; j++) {
			pfs2[j][i] = pfs2[j - 1][i];
			if (grid[j - 1][i] == 'X')
				pfs2[j][i]++;
		}
	}
/*	cout<<"pfs1: "<<endl;
	for (vi v : pfs1) {
		for (int x : v)
			cout<<x<<" ";
		cout<<endl;
	}
	cout<<"pfs2: "<<endl;
	for (vi v : pfs2) {
		for (int x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<vector<vector<vector<bool>>>> vis(R, vector<vector<vector<bool>>>(C, vector<vector<bool>>(R, vector<bool>(C, false))));
	set<pair<ii, ii>> visited;
	queue<pair<ii, ii>> q;
	vis[start.fi.fi][start.fi.se][start.se.fi][start.se.se] = true;
	q.push(start);
	while (!q.empty()) {
		pair<ii, ii> x = q.front();
		q.pop();
//		cout<<"at ("<<x.fi.fi<<", "<<x.fi.se<<", "<<x.se.fi<<", "<<x.se.se<<")"<<endl;
		for (int i = 0; i < 8; i++) {
			pair<ii, ii> y = x;	// new state
			y.fi.fi += dir1[i];
			y.fi.se += dir2[i];
			y.se.fi += dir3[i];
			y.se.se += dir4[i];
//			cout<<"going to ("<<y.fi.fi<<", "<<y.fi.se<<", "<<y.se.fi<<", "<<y.se.se<<")"<<endl;
			// check if state is possible
			if (y.fi.fi < 0 || y.fi.fi >= R || y.fi.se < 0 || y.fi.se >= C - K + 1)
				continue;
			if (y.se.se < 0 || y.se.se >= C || y.se.fi < 0 || y.se.fi >= R - L + 1)
				continue;
			// check if they intersect
			if (y.fi.fi < y.se.fi || y.fi.fi >= y.se.fi + L)
				continue;
			if (y.se.se < y.fi.se || y.se.se >= y.fi.se + K)
				continue;
			// state is in grid, check if none on it blocked
			if (pfs1[y.fi.fi][y.fi.se + K] - pfs1[y.fi.fi][y.fi.se] > 0)
				continue;
			if (pfs2[y.se.fi + L][y.se.se] - pfs2[y.se.fi][y.se.se] > 0)
				continue;
			// if state is possible and unvisited, add to queue
			if (!vis[y.fi.fi][y.fi.se][y.se.fi][y.se.se]) {
				q.push(y);
				vis[y.fi.fi][y.fi.se][y.se.fi][y.se.se] = true;
			}
		}
	}
	// check if any of visited intersect at flag
	bool found = false;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			for (int k = 0; k < R; k++) {
				for (int l = 0; l < C; l++) {
					if (vis[i][j][k][l]) {
//						cout<<"can do "<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
						ii ins = {i, l};
						if (ins == goal)
							found = true;
					}
				}
			}
		}
	}
	if (found)
		cout<<"YES"<<endl;
	else
		cout<<"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