oj.uz

Submission #1077107

# Submission time Handle Problem Language Result Execution time Memory
1077107 2024-08-27T00:45:51 Z pawned Toy (CEOI24_toy) C++17
0 / 100
 1073 ms 1048576 KB 
#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;
			// 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]) {
						ii ist = {i, l};
						if (ist == goal)
							found = true;
					}
				}
			}
		}
	}
	if (found)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 166 ms 10076 KB Output is correct
5 Correct 19 ms 9340 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 20 ms 9512 KB Output is correct
8 Correct 20 ms 9560 KB Output is correct
9 Correct 4 ms 2652 KB Output is correct
10 Correct 18 ms 9384 KB Output is correct
11 Correct 20 ms 9560 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 22 ms 9460 KB Output is correct
14 Correct 19 ms 9572 KB Output is correct
15 Incorrect 123 ms 9500 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 166 ms 10076 KB Output is correct
5 Correct 19 ms 9340 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 20 ms 9512 KB Output is correct
8 Correct 20 ms 9560 KB Output is correct
9 Correct 4 ms 2652 KB Output is correct
10 Correct 18 ms 9384 KB Output is correct
11 Correct 20 ms 9560 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 22 ms 9460 KB Output is correct
14 Correct 19 ms 9572 KB Output is correct
15 Incorrect 123 ms 9500 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 500 ms 9392 KB Output is correct
4 Runtime error 1073 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 166 ms 10076 KB Output is correct
5 Correct 19 ms 9340 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 20 ms 9512 KB Output is correct
8 Correct 20 ms 9560 KB Output is correct
9 Correct 4 ms 2652 KB Output is correct
10 Correct 18 ms 9384 KB Output is correct
11 Correct 20 ms 9560 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 22 ms 9460 KB Output is correct
14 Correct 19 ms 9572 KB Output is correct
15 Incorrect 123 ms 9500 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 166 ms 10076 KB Output is correct
5 Correct 19 ms 9340 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 20 ms 9512 KB Output is correct
8 Correct 20 ms 9560 KB Output is correct
9 Correct 4 ms 2652 KB Output is correct
10 Correct 18 ms 9384 KB Output is correct
11 Correct 20 ms 9560 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 22 ms 9460 KB Output is correct
14 Correct 19 ms 9572 KB Output is correct
15 Incorrect 123 ms 9500 KB Output isn't correct
16 Halted 0 ms 0 KB -