oj.uz

Submission #1045724

# Submission time Handle Problem Language Result Execution time Memory
1045724 2024-08-06T07:12:02 Z alex_2008 Toy (CEOI24_toy) C++14
9 / 100
 10 ms 17244 KB 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
typedef long long ll;
using namespace std;
const int N = 1510;
char a[N][N];
bool used[N][N];
int tp[N][N];
int dwn[N][N];
int lft[N][N];
int rght[N][N];
int w, h, k, l;
int cnt(int x1, int y1, int x2, int y2) {
	return a[x2][y2] - a[x1][y2] - a[x2][y1] + a[x1][y1];
}
pair<int, int> vertical_range(int x, int y) {
	if (tp[x][y] + dwn[x][y] <= l) return { 1, 0 };
	int r_min = x - tp[x][y] + 1;
	int r_mx = x + dwn[x][y] - l;
	return make_pair(r_min, r_mx);
}
pair<int, int> horizontal_range(int x, int y) {
	if (lft[x][y] + rght[x][y] <= k) return { 1, 0 };
	int c_min = x - lft[x][y] + 1;
	int c_mx = x + rght[x][y] - k;
	return make_pair(c_min, c_mx);
}
bool intersect(pair<int, int> x, pair<int, int> y) {
	pair<int, int> c = make_pair(max(x.first, y.first), min(x.second, y.second));
	if (c.first > c.second) return false;
	return true;
}
bool ch(int x, int y) {
	if ((tp[x][y] + dwn[x][y]) > l && (lft[x][y] + rght[x][y]) > k) return true;
	return false;
}
int main() {
	cin >> w >> h >> k >> l;
	int xh, yh, xv, yv;
	cin >> xh >> yh >> xv >> yv;
	xh++; xv++; yh++; yv++;
	swap(xh, yh); swap(xv, yv);
	//cout << xh << " " << yh << " " << xv << " " << yv << "\n";
	int fx = -1, fy = -1;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> a[i][j];
			if (a[i][j] == '*') {
				fx = i;
				fy = j;
			}
		}
	}

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (a[i][j] == 'X') {
				lft[i][j] = 0;
				tp[i][j] = 0;
			}
			else {
				lft[i][j] = lft[i][j - 1] + 1;
				tp[i][j] = tp[i - 1][j] + 1;
			}
			lft[i][j] = min(lft[i][j], k);
			tp[i][j] = min(tp[i][j], l);

		}
	}
	for (int i = h; i >= 1; i--) {
		for (int j = w; j >= 1; j--) {
			if (a[i][j] == 'X') {
				rght[i][j] = 0;
				dwn[i][j] = 0;
			}
			else {
				rght[i][j] = rght[i][j + 1] + 1;
				dwn[i][j] = dwn[i + 1][j] + 1;
			}
			rght[i][j] = min(rght[i][j], k);
			dwn[i][j] = min(dwn[i][j], l);
		}
	}
	used[xh][yv] = true;
	queue <pair<int, int>> Q;
	Q.push({ xh, yv });
	while (!Q.empty()) {
		int x = Q.front().first, y = Q.front().second; Q.pop();
		//cout << "? " << x << " " << y << "\n";
		if (x > 1) {
			if (intersect(horizontal_range(x, y), horizontal_range(x - 1, y)) && ch(x - 1, y)) {
				if (!used[x - 1][y]) {
					used[x - 1][y] = true;
					Q.push({ x - 1, y });
				}
			}
		}
		if (x < h) {
			if (intersect(horizontal_range(x, y), horizontal_range(x + 1, y)) && ch(x + 1, y)) {
				if (!used[x + 1][y]) {
					used[x + 1][y] = true;
					Q.push({ x + 1, y });
				}
			}
		}
		if (y > 1) {
			if (intersect(vertical_range(x, y), vertical_range(x, y - 1)) && ch(x, y - 1)) {
				if (!used[x][y - 1]) {
					used[x][y - 1] = true;
					Q.push({ x, y - 1 });
				}
			}
		}
		if (y < w) {
			if (intersect(vertical_range(x, y), vertical_range(x, y + 1)) && ch(x, y + 1)) {
				if (!used[x][y + 1]) {
					used[x][y + 1] = true;
					Q.push({ x, y + 1 });
				}
			}
		}
	}
	if (used[fx][fy]) cout << "YES\n";
	else cout << "NO\n";
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7260 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 1 ms 7260 KB Output is correct
11 Correct 1 ms 7068 KB Output is correct
12 Correct 0 ms 6492 KB Output is correct
13 Correct 1 ms 11100 KB Output is correct
14 Correct 1 ms 11100 KB Output is correct
15 Correct 1 ms 7260 KB Output is correct
16 Correct 1 ms 7004 KB Output is correct
17 Correct 1 ms 7004 KB Output is correct
18 Correct 1 ms 7260 KB Output is correct
19 Correct 1 ms 7260 KB Output is correct
20 Correct 1 ms 7260 KB Output is correct
21 Correct 1 ms 7260 KB Output is correct
22 Correct 1 ms 7260 KB Output is correct
23 Correct 1 ms 7260 KB Output is correct
24 Correct 1 ms 7260 KB Output is correct
25 Correct 1 ms 7256 KB Output is correct
26 Correct 1 ms 7076 KB Output is correct
27 Correct 1 ms 7256 KB Output is correct
28 Correct 2 ms 7260 KB Output is correct
29 Correct 1 ms 7260 KB Output is correct
30 Correct 1 ms 7260 KB Output is correct
31 Correct 1 ms 7244 KB Output is correct
32 Correct 1 ms 7260 KB Output is correct
33 Correct 1 ms 7260 KB Output is correct
34 Correct 1 ms 7260 KB Output is correct
35 Correct 1 ms 7260 KB Output is correct
36 Correct 1 ms 7260 KB Output is correct
37 Correct 1 ms 7004 KB Output is correct
38 Correct 1 ms 7260 KB Output is correct
39 Correct 1 ms 7004 KB Output is correct
40 Correct 1 ms 7260 KB Output is correct
41 Correct 1 ms 7256 KB Output is correct
42 Incorrect 1 ms 7260 KB Output isn't correct
43 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7260 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 1 ms 7260 KB Output is correct
11 Correct 1 ms 7068 KB Output is correct
12 Correct 0 ms 6492 KB Output is correct
13 Correct 1 ms 11100 KB Output is correct
14 Correct 1 ms 11100 KB Output is correct
15 Correct 1 ms 7260 KB Output is correct
16 Correct 1 ms 7004 KB Output is correct
17 Correct 1 ms 7004 KB Output is correct
18 Correct 1 ms 7260 KB Output is correct
19 Correct 1 ms 7260 KB Output is correct
20 Correct 1 ms 7260 KB Output is correct
21 Correct 1 ms 7260 KB Output is correct
22 Correct 1 ms 7260 KB Output is correct
23 Correct 1 ms 7260 KB Output is correct
24 Correct 1 ms 7260 KB Output is correct
25 Correct 1 ms 7256 KB Output is correct
26 Correct 1 ms 7076 KB Output is correct
27 Correct 1 ms 7256 KB Output is correct
28 Correct 2 ms 7260 KB Output is correct
29 Correct 1 ms 7260 KB Output is correct
30 Correct 1 ms 7260 KB Output is correct
31 Correct 1 ms 7244 KB Output is correct
32 Correct 1 ms 7260 KB Output is correct
33 Correct 1 ms 7260 KB Output is correct
34 Correct 1 ms 7260 KB Output is correct
35 Correct 1 ms 7260 KB Output is correct
36 Correct 1 ms 7260 KB Output is correct
37 Correct 1 ms 7004 KB Output is correct
38 Correct 1 ms 7260 KB Output is correct
39 Correct 1 ms 7004 KB Output is correct
40 Correct 1 ms 7260 KB Output is correct
41 Correct 1 ms 7256 KB Output is correct
42 Incorrect 1 ms 7260 KB Output isn't correct
43 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 6 ms 12696 KB Output is correct
5 Correct 7 ms 12636 KB Output is correct
6 Correct 1 ms 7516 KB Output is correct
7 Correct 6 ms 12636 KB Output is correct
8 Correct 7 ms 12636 KB Output is correct
9 Correct 2 ms 11356 KB Output is correct
10 Correct 5 ms 12492 KB Output is correct
11 Correct 4 ms 12636 KB Output is correct
12 Correct 2 ms 13912 KB Output is correct
13 Correct 4 ms 15196 KB Output is correct
14 Correct 4 ms 17244 KB Output is correct
15 Correct 6 ms 12380 KB Output is correct
16 Correct 10 ms 12396 KB Output is correct
17 Correct 6 ms 12380 KB Output is correct
18 Correct 10 ms 12636 KB Output is correct
19 Correct 6 ms 12636 KB Output is correct
20 Correct 7 ms 12692 KB Output is correct
21 Correct 7 ms 12448 KB Output is correct
22 Correct 7 ms 12476 KB Output is correct
23 Correct 7 ms 12632 KB Output is correct
24 Correct 6 ms 12636 KB Output is correct
25 Correct 10 ms 12696 KB Output is correct
26 Correct 6 ms 12632 KB Output is correct
27 Correct 6 ms 12636 KB Output is correct
28 Correct 6 ms 12476 KB Output is correct
29 Correct 6 ms 12636 KB Output is correct
30 Correct 6 ms 12380 KB Output is correct
31 Correct 6 ms 12380 KB Output is correct
32 Correct 6 ms 12448 KB Output is correct
33 Correct 9 ms 12380 KB Output is correct
34 Correct 6 ms 12124 KB Output is correct
35 Correct 6 ms 12380 KB Output is correct
36 Correct 6 ms 12380 KB Output is correct
37 Correct 6 ms 12380 KB Output is correct
38 Correct 5 ms 12380 KB Output is correct
39 Correct 5 ms 12380 KB Output is correct
40 Correct 5 ms 12472 KB Output is correct
41 Correct 5 ms 12376 KB Output is correct
42 Correct 7 ms 12636 KB Output is correct
43 Correct 7 ms 12888 KB Output is correct
44 Correct 7 ms 12636 KB Output is correct
45 Correct 10 ms 12636 KB Output is correct
46 Correct 3 ms 14428 KB Output is correct

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7260 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 1 ms 7260 KB Output is correct
11 Correct 1 ms 7068 KB Output is correct
12 Correct 0 ms 6492 KB Output is correct
13 Correct 1 ms 11100 KB Output is correct
14 Correct 1 ms 11100 KB Output is correct
15 Correct 1 ms 7260 KB Output is correct
16 Correct 1 ms 7004 KB Output is correct
17 Correct 1 ms 7004 KB Output is correct
18 Correct 1 ms 7260 KB Output is correct
19 Correct 1 ms 7260 KB Output is correct
20 Correct 1 ms 7260 KB Output is correct
21 Correct 1 ms 7260 KB Output is correct
22 Correct 1 ms 7260 KB Output is correct
23 Correct 1 ms 7260 KB Output is correct
24 Correct 1 ms 7260 KB Output is correct
25 Correct 1 ms 7256 KB Output is correct
26 Correct 1 ms 7076 KB Output is correct
27 Correct 1 ms 7256 KB Output is correct
28 Correct 2 ms 7260 KB Output is correct
29 Correct 1 ms 7260 KB Output is correct
30 Correct 1 ms 7260 KB Output is correct
31 Correct 1 ms 7244 KB Output is correct
32 Correct 1 ms 7260 KB Output is correct
33 Correct 1 ms 7260 KB Output is correct
34 Correct 1 ms 7260 KB Output is correct
35 Correct 1 ms 7260 KB Output is correct
36 Correct 1 ms 7260 KB Output is correct
37 Correct 1 ms 7004 KB Output is correct
38 Correct 1 ms 7260 KB Output is correct
39 Correct 1 ms 7004 KB Output is correct
40 Correct 1 ms 7260 KB Output is correct
41 Correct 1 ms 7256 KB Output is correct
42 Incorrect 1 ms 7260 KB Output isn't correct
43 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 7260 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 1 ms 7260 KB Output is correct
8 Correct 1 ms 7260 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 1 ms 7260 KB Output is correct
11 Correct 1 ms 7068 KB Output is correct
12 Correct 0 ms 6492 KB Output is correct
13 Correct 1 ms 11100 KB Output is correct
14 Correct 1 ms 11100 KB Output is correct
15 Correct 1 ms 7260 KB Output is correct
16 Correct 1 ms 7004 KB Output is correct
17 Correct 1 ms 7004 KB Output is correct
18 Correct 1 ms 7260 KB Output is correct
19 Correct 1 ms 7260 KB Output is correct
20 Correct 1 ms 7260 KB Output is correct
21 Correct 1 ms 7260 KB Output is correct
22 Correct 1 ms 7260 KB Output is correct
23 Correct 1 ms 7260 KB Output is correct
24 Correct 1 ms 7260 KB Output is correct
25 Correct 1 ms 7256 KB Output is correct
26 Correct 1 ms 7076 KB Output is correct
27 Correct 1 ms 7256 KB Output is correct
28 Correct 2 ms 7260 KB Output is correct
29 Correct 1 ms 7260 KB Output is correct
30 Correct 1 ms 7260 KB Output is correct
31 Correct 1 ms 7244 KB Output is correct
32 Correct 1 ms 7260 KB Output is correct
33 Correct 1 ms 7260 KB Output is correct
34 Correct 1 ms 7260 KB Output is correct
35 Correct 1 ms 7260 KB Output is correct
36 Correct 1 ms 7260 KB Output is correct
37 Correct 1 ms 7004 KB Output is correct
38 Correct 1 ms 7260 KB Output is correct
39 Correct 1 ms 7004 KB Output is correct
40 Correct 1 ms 7260 KB Output is correct
41 Correct 1 ms 7256 KB Output is correct
42 Incorrect 1 ms 7260 KB Output isn't correct
43 Halted 0 ms 0 KB -