Submission #1045645

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1045645	2024-08-06T06:43:16 Z	Tsovak	Toy (CEOI24_toy)	C++17	0 / 100	23 ms	66544 KB

Main

// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

// -------------------- Typedefs -------------------- //

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// -------------------- Defines -------------------- //

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue

#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()

#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back

#define lb lower_bound
#define ub upper_bound
#define bs binary_search

// -------------------- Constants -------------------- //

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

// -------------------- Functions -------------------- //

void fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return;
}

void precision(int x)
{
	cout << fixed << setprecision(x);
	return;
}

ll gcd0(ll a, ll b)
{
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

ll lcm0(ll a, ll b)
{
	return a / gcd0(a, b) * b;
}

bool is_prime(ll a)
{
	if (a == 1) return false;
	for (ll i = 2; i * i <= a; i++) if (a % i == 0) return false;
	return true;
}

bool is_square(ll a)
{
	ll b = ll(sqrtl(ld(a)));
	return (b * b == a);
}

bool is_cube(ll a)
{
	ll b = ll(cbrtl(ld(a)));
	return (b * b * b == a);
}

int digit_sum(ll a)
{
	int sum = 0;
	while (a) {
		sum += int(a % 10);
		a /= 10;
	}
	return sum;
}

ll binpow(ll a, int b)
{
	ll ans = 1;
	while (b) {
		if (b & 1) ans *= a;
		b >>= 1;
		a *= a;
	}
	return ans;
}

ll binpow_mod(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b) {
		if (b & 1) ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans;
}

ll factorial(int a)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) ans *= ll(i);
	return ans;
}

ll factorial_mod(int a, ll mod)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) ans = (ans * ll(i)) % mod;
	return ans;
}

// -------------------- Solution -------------------- //

const int N = 1505, M = 1505;
char a[N][M];
int px[N], py[M];
vector<pr<int, int>> g[N][M];
int n, m, k, l;
int xh, yh, xv, yv, tx, ty;

vector<int> vx[N], vy[M];

bool used[N][M];

void dfs(int x, int y)
{
	used[x][y] = true;

	for (int i = 0; i < sz(g[x][y]); i++) {
		if (!used[g[x][y][i].ff][g[x][y][i].ss]) dfs(g[x][y][i].ff, g[x][y][i].ss);
	}

	return;
}

void solve()
{
	int i, j;

	cin >> m >> n >> k >> l;
	cin >> yh >> xh >> yv >> xv;

	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			cin >> a[i][j];

			if (a[i][j] == '*') {
				tx = i;
				ty = j;
			}
			else if (a[i][j] == 'X') {
				vx[i].pb(j);
				vy[j].pb(i);
			}
		}
	}

	for (j = 1; j <= m; j++) sort(all(vy[j]));

	int h, cnt;
	int lx, rx, ly, ry;

	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			if (a[i][j] == 'X') continue;

			h = ub(all(vy[j]), i) - vy[j].begin();

			if (h == sz(vy[j])) rx = n;
			else rx = vy[j][h];
			rx = min(rx, i + l - 1);

			h--;
			if (h < 0) lx = 1;
			else lx = vy[j][h];
			lx = max(lx, i - l + 1);


			h = ub(all(vx[i]), j) - vx[i].begin();

			if (h == sz(vx[i])) ry = m;
			else ry = vx[i][h];
			ry = min(ry, j + k - 1);

			h--;
			if (h < 0) ly = 1;
			else ly = vx[i][h];
			ly = max(ly, j - k + 1);


			if (l > rx - lx + 1 || k > ry - ly + 1) continue;

			if (i < n && rx >= i + 1) {
				cnt = 0;

				for (h = ly; h <= ry; h++) {
					if (a[i + 1][h] == 'X') cnt = 0;
					else cnt++;

					if (cnt >= k) {
						g[i][j].pb(mpr(i + 1, j));
						g[i + 1][j].pb(mpr(i, j));

						break;
					}
				}
			}

			if (j < m && ry >= j + 1) {
				cnt = 0;

				for (h = lx; h <= rx; h++) {
					if (a[h][j + 1] == 'X') cnt = 0;
					else cnt++;

					if (cnt >= l) {
						g[i][j].pb(mpr(i, j + 1));
						g[i][j + 1].pb(mpr(i, j));

						break;
					}
				}
			}
		}
	}

	dfs(xh + 1, yv + 1);

	if (used[tx][ty]) cout << "YES\n";
	else cout << "NO\n";

	return;
}

void precalc()
{
	return;
}

int main()
{
	fastio();

	precalc();

	int tests = 1, tc;
	//cin >> tests;
	for (tc = 1; tc <= tests; tc++) {
		solve();
	}

	return 0;
}

/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	55644 KB	Output is correct
2	Correct	7 ms	55644 KB	Output is correct

Subtask #1
0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	55644 KB	Output is correct
2	Correct	7 ms	55644 KB	Output is correct
3	Correct	8 ms	55896 KB	Output is correct
4	Correct	8 ms	56156 KB	Output is correct
5	Correct	7 ms	55900 KB	Output is correct
6	Correct	7 ms	55784 KB	Output is correct
7	Correct	8 ms	55900 KB	Output is correct
8	Correct	7 ms	55820 KB	Output is correct
9	Correct	7 ms	55644 KB	Output is correct
10	Correct	8 ms	55644 KB	Output is correct
11	Correct	8 ms	55872 KB	Output is correct
12	Correct	8 ms	55644 KB	Output is correct
13	Correct	7 ms	55896 KB	Output is correct
14	Correct	7 ms	55640 KB	Output is correct
15	Correct	7 ms	56128 KB	Output is correct
16	Correct	8 ms	55900 KB	Output is correct
17	Correct	8 ms	56052 KB	Output is correct
18	Correct	8 ms	56156 KB	Output is correct
19	Correct	8 ms	56156 KB	Output is correct
20	Correct	7 ms	56016 KB	Output is correct
21	Correct	7 ms	56156 KB	Output is correct
22	Correct	8 ms	56156 KB	Output is correct
23	Correct	8 ms	56156 KB	Output is correct
24	Correct	8 ms	56176 KB	Output is correct
25	Correct	8 ms	56156 KB	Output is correct
26	Correct	8 ms	56032 KB	Output is correct
27	Correct	9 ms	55900 KB	Output is correct
28	Correct	8 ms	55896 KB	Output is correct
29	Correct	8 ms	56040 KB	Output is correct
30	Correct	8 ms	56008 KB	Output is correct
31	Incorrect	9 ms	55900 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #2
0.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	55644 KB	Output is correct
2	Correct	7 ms	55644 KB	Output is correct
3	Correct	8 ms	55896 KB	Output is correct
4	Correct	8 ms	56156 KB	Output is correct
5	Correct	7 ms	55900 KB	Output is correct
6	Correct	7 ms	55784 KB	Output is correct
7	Correct	8 ms	55900 KB	Output is correct
8	Correct	7 ms	55820 KB	Output is correct
9	Correct	7 ms	55644 KB	Output is correct
10	Correct	8 ms	55644 KB	Output is correct
11	Correct	8 ms	55872 KB	Output is correct
12	Correct	8 ms	55644 KB	Output is correct
13	Correct	7 ms	55896 KB	Output is correct
14	Correct	7 ms	55640 KB	Output is correct
15	Correct	7 ms	56128 KB	Output is correct
16	Correct	8 ms	55900 KB	Output is correct
17	Correct	8 ms	56052 KB	Output is correct
18	Correct	8 ms	56156 KB	Output is correct
19	Correct	8 ms	56156 KB	Output is correct
20	Correct	7 ms	56016 KB	Output is correct
21	Correct	7 ms	56156 KB	Output is correct
22	Correct	8 ms	56156 KB	Output is correct
23	Correct	8 ms	56156 KB	Output is correct
24	Correct	8 ms	56176 KB	Output is correct
25	Correct	8 ms	56156 KB	Output is correct
26	Correct	8 ms	56032 KB	Output is correct
27	Correct	9 ms	55900 KB	Output is correct
28	Correct	8 ms	55896 KB	Output is correct
29	Correct	8 ms	56040 KB	Output is correct
30	Correct	8 ms	56008 KB	Output is correct
31	Incorrect	9 ms	55900 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #3
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	55644 KB	Output is correct
2	Correct	7 ms	55644 KB	Output is correct
3	Correct	9 ms	56152 KB	Output is correct
4	Correct	20 ms	66212 KB	Output is correct
5	Correct	21 ms	66392 KB	Output is correct
6	Correct	9 ms	58972 KB	Output is correct
7	Correct	20 ms	64932 KB	Output is correct
8	Correct	23 ms	65364 KB	Output is correct
9	Correct	12 ms	58712 KB	Output is correct
10	Correct	18 ms	61016 KB	Output is correct
11	Correct	17 ms	59736 KB	Output is correct
12	Correct	9 ms	57948 KB	Output is correct
13	Correct	12 ms	58360 KB	Output is correct
14	Correct	12 ms	58204 KB	Output is correct
15	Correct	18 ms	65884 KB	Output is correct
16	Correct	18 ms	65628 KB	Output is correct
17	Correct	20 ms	65628 KB	Output is correct
18	Correct	19 ms	66396 KB	Output is correct
19	Correct	19 ms	66336 KB	Output is correct
20	Correct	21 ms	66396 KB	Output is correct
21	Correct	21 ms	66396 KB	Output is correct
22	Correct	20 ms	66396 KB	Output is correct
23	Correct	21 ms	66396 KB	Output is correct
24	Correct	20 ms	66396 KB	Output is correct
25	Correct	19 ms	66544 KB	Output is correct
26	Correct	21 ms	64788 KB	Output is correct
27	Correct	18 ms	64856 KB	Output is correct
28	Correct	22 ms	64856 KB	Output is correct
29	Correct	22 ms	64696 KB	Output is correct
30	Correct	23 ms	66140 KB	Output is correct
31	Incorrect	19 ms	65884 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	55644 KB	Output is correct
2	Correct	7 ms	55644 KB	Output is correct
3	Correct	8 ms	55896 KB	Output is correct
4	Correct	8 ms	56156 KB	Output is correct
5	Correct	7 ms	55900 KB	Output is correct
6	Correct	7 ms	55784 KB	Output is correct
7	Correct	8 ms	55900 KB	Output is correct
8	Correct	7 ms	55820 KB	Output is correct
9	Correct	7 ms	55644 KB	Output is correct
10	Correct	8 ms	55644 KB	Output is correct
11	Correct	8 ms	55872 KB	Output is correct
12	Correct	8 ms	55644 KB	Output is correct
13	Correct	7 ms	55896 KB	Output is correct
14	Correct	7 ms	55640 KB	Output is correct
15	Correct	7 ms	56128 KB	Output is correct
16	Correct	8 ms	55900 KB	Output is correct
17	Correct	8 ms	56052 KB	Output is correct
18	Correct	8 ms	56156 KB	Output is correct
19	Correct	8 ms	56156 KB	Output is correct
20	Correct	7 ms	56016 KB	Output is correct
21	Correct	7 ms	56156 KB	Output is correct
22	Correct	8 ms	56156 KB	Output is correct
23	Correct	8 ms	56156 KB	Output is correct
24	Correct	8 ms	56176 KB	Output is correct
25	Correct	8 ms	56156 KB	Output is correct
26	Correct	8 ms	56032 KB	Output is correct
27	Correct	9 ms	55900 KB	Output is correct
28	Correct	8 ms	55896 KB	Output is correct
29	Correct	8 ms	56040 KB	Output is correct
30	Correct	8 ms	56008 KB	Output is correct
31	Incorrect	9 ms	55900 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	55644 KB	Output is correct
2	Correct	7 ms	55644 KB	Output is correct
3	Correct	8 ms	55896 KB	Output is correct
4	Correct	8 ms	56156 KB	Output is correct
5	Correct	7 ms	55900 KB	Output is correct
6	Correct	7 ms	55784 KB	Output is correct
7	Correct	8 ms	55900 KB	Output is correct
8	Correct	7 ms	55820 KB	Output is correct
9	Correct	7 ms	55644 KB	Output is correct
10	Correct	8 ms	55644 KB	Output is correct
11	Correct	8 ms	55872 KB	Output is correct
12	Correct	8 ms	55644 KB	Output is correct
13	Correct	7 ms	55896 KB	Output is correct
14	Correct	7 ms	55640 KB	Output is correct
15	Correct	7 ms	56128 KB	Output is correct
16	Correct	8 ms	55900 KB	Output is correct
17	Correct	8 ms	56052 KB	Output is correct
18	Correct	8 ms	56156 KB	Output is correct
19	Correct	8 ms	56156 KB	Output is correct
20	Correct	7 ms	56016 KB	Output is correct
21	Correct	7 ms	56156 KB	Output is correct
22	Correct	8 ms	56156 KB	Output is correct
23	Correct	8 ms	56156 KB	Output is correct
24	Correct	8 ms	56176 KB	Output is correct
25	Correct	8 ms	56156 KB	Output is correct
26	Correct	8 ms	56032 KB	Output is correct
27	Correct	9 ms	55900 KB	Output is correct
28	Correct	8 ms	55896 KB	Output is correct
29	Correct	8 ms	56040 KB	Output is correct
30	Correct	8 ms	56008 KB	Output is correct
31	Incorrect	9 ms	55900 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Submission #1045645

Compilation message

Subtask #0 0.0 / 0.0

Subtask #1 0.0 / 14.0

Subtask #2 0.0 / 21.0

Subtask #3 0.0 / 9.0

Subtask #4 0.0 / 29.0

Subtask #5 0.0 / 27.0

Subtask #0
0.0 / 0.0

Subtask #1
0.0 / 14.0

Subtask #2
0.0 / 21.0

Subtask #3
0.0 / 9.0

Subtask #4
0.0 / 29.0

Subtask #5
0.0 / 27.0