Submission #1045663

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1045663	2024-08-06T06:49:16 Z	Tsovak	Toy (CEOI24_toy)	C++17	0 / 100	36 ms	63076 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)
{
	if (a[x][y] == 'X') return;

	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 && a[i + 1][j] != 'X') {
				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 && a[i][j + 1] != 'X') {
				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	11 ms	53596 KB	Output is correct
2	Correct	12 ms	53596 KB	Output is correct

Subtask #1
0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	53596 KB	Output is correct
2	Correct	12 ms	53596 KB	Output is correct
3	Correct	11 ms	53576 KB	Output is correct
4	Correct	12 ms	54112 KB	Output is correct
5	Correct	13 ms	53852 KB	Output is correct
6	Correct	13 ms	53880 KB	Output is correct
7	Correct	11 ms	53728 KB	Output is correct
8	Correct	11 ms	53852 KB	Output is correct
9	Correct	11 ms	53756 KB	Output is correct
10	Correct	11 ms	53596 KB	Output is correct
11	Correct	11 ms	53816 KB	Output is correct
12	Correct	11 ms	53596 KB	Output is correct
13	Correct	12 ms	53596 KB	Output is correct
14	Correct	14 ms	53828 KB	Output is correct
15	Correct	11 ms	53852 KB	Output is correct
16	Correct	12 ms	53964 KB	Output is correct
17	Correct	11 ms	54072 KB	Output is correct
18	Correct	11 ms	54120 KB	Output is correct
19	Correct	15 ms	54108 KB	Output is correct
20	Correct	11 ms	54108 KB	Output is correct
21	Correct	13 ms	53984 KB	Output is correct
22	Correct	16 ms	54076 KB	Output is correct
23	Correct	12 ms	54092 KB	Output is correct
24	Correct	11 ms	54108 KB	Output is correct
25	Correct	11 ms	53860 KB	Output is correct
26	Correct	13 ms	53852 KB	Output is correct
27	Correct	12 ms	53852 KB	Output is correct
28	Correct	14 ms	53852 KB	Output is correct
29	Correct	16 ms	53852 KB	Output is correct
30	Correct	11 ms	53940 KB	Output is correct
31	Incorrect	17 ms	53852 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	11 ms	53596 KB	Output is correct
2	Correct	12 ms	53596 KB	Output is correct
3	Correct	11 ms	53576 KB	Output is correct
4	Correct	12 ms	54112 KB	Output is correct
5	Correct	13 ms	53852 KB	Output is correct
6	Correct	13 ms	53880 KB	Output is correct
7	Correct	11 ms	53728 KB	Output is correct
8	Correct	11 ms	53852 KB	Output is correct
9	Correct	11 ms	53756 KB	Output is correct
10	Correct	11 ms	53596 KB	Output is correct
11	Correct	11 ms	53816 KB	Output is correct
12	Correct	11 ms	53596 KB	Output is correct
13	Correct	12 ms	53596 KB	Output is correct
14	Correct	14 ms	53828 KB	Output is correct
15	Correct	11 ms	53852 KB	Output is correct
16	Correct	12 ms	53964 KB	Output is correct
17	Correct	11 ms	54072 KB	Output is correct
18	Correct	11 ms	54120 KB	Output is correct
19	Correct	15 ms	54108 KB	Output is correct
20	Correct	11 ms	54108 KB	Output is correct
21	Correct	13 ms	53984 KB	Output is correct
22	Correct	16 ms	54076 KB	Output is correct
23	Correct	12 ms	54092 KB	Output is correct
24	Correct	11 ms	54108 KB	Output is correct
25	Correct	11 ms	53860 KB	Output is correct
26	Correct	13 ms	53852 KB	Output is correct
27	Correct	12 ms	53852 KB	Output is correct
28	Correct	14 ms	53852 KB	Output is correct
29	Correct	16 ms	53852 KB	Output is correct
30	Correct	11 ms	53940 KB	Output is correct
31	Incorrect	17 ms	53852 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	11 ms	53596 KB	Output is correct
2	Correct	12 ms	53596 KB	Output is correct
3	Correct	15 ms	54108 KB	Output is correct
4	Correct	23 ms	62836 KB	Output is correct
5	Correct	29 ms	62852 KB	Output is correct
6	Correct	13 ms	54872 KB	Output is correct
7	Correct	30 ms	61632 KB	Output is correct
8	Correct	27 ms	62032 KB	Output is correct
9	Correct	21 ms	54620 KB	Output is correct
10	Correct	22 ms	57104 KB	Output is correct
11	Correct	21 ms	55900 KB	Output is correct
12	Correct	17 ms	54052 KB	Output is correct
13	Correct	19 ms	54620 KB	Output is correct
14	Correct	15 ms	54376 KB	Output is correct
15	Correct	22 ms	62416 KB	Output is correct
16	Correct	26 ms	61888 KB	Output is correct
17	Correct	23 ms	62040 KB	Output is correct
18	Correct	24 ms	63076 KB	Output is correct
19	Correct	22 ms	62848 KB	Output is correct
20	Correct	26 ms	63056 KB	Output is correct
21	Correct	23 ms	63056 KB	Output is correct
22	Correct	24 ms	62888 KB	Output is correct
23	Correct	21 ms	63068 KB	Output is correct
24	Correct	26 ms	62824 KB	Output is correct
25	Correct	27 ms	62812 KB	Output is correct
26	Correct	22 ms	61272 KB	Output is correct
27	Correct	22 ms	61252 KB	Output is correct
28	Correct	24 ms	61276 KB	Output is correct
29	Correct	22 ms	61368 KB	Output is correct
30	Correct	36 ms	62736 KB	Output is correct
31	Incorrect	34 ms	62188 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	11 ms	53596 KB	Output is correct
2	Correct	12 ms	53596 KB	Output is correct
3	Correct	11 ms	53576 KB	Output is correct
4	Correct	12 ms	54112 KB	Output is correct
5	Correct	13 ms	53852 KB	Output is correct
6	Correct	13 ms	53880 KB	Output is correct
7	Correct	11 ms	53728 KB	Output is correct
8	Correct	11 ms	53852 KB	Output is correct
9	Correct	11 ms	53756 KB	Output is correct
10	Correct	11 ms	53596 KB	Output is correct
11	Correct	11 ms	53816 KB	Output is correct
12	Correct	11 ms	53596 KB	Output is correct
13	Correct	12 ms	53596 KB	Output is correct
14	Correct	14 ms	53828 KB	Output is correct
15	Correct	11 ms	53852 KB	Output is correct
16	Correct	12 ms	53964 KB	Output is correct
17	Correct	11 ms	54072 KB	Output is correct
18	Correct	11 ms	54120 KB	Output is correct
19	Correct	15 ms	54108 KB	Output is correct
20	Correct	11 ms	54108 KB	Output is correct
21	Correct	13 ms	53984 KB	Output is correct
22	Correct	16 ms	54076 KB	Output is correct
23	Correct	12 ms	54092 KB	Output is correct
24	Correct	11 ms	54108 KB	Output is correct
25	Correct	11 ms	53860 KB	Output is correct
26	Correct	13 ms	53852 KB	Output is correct
27	Correct	12 ms	53852 KB	Output is correct
28	Correct	14 ms	53852 KB	Output is correct
29	Correct	16 ms	53852 KB	Output is correct
30	Correct	11 ms	53940 KB	Output is correct
31	Incorrect	17 ms	53852 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	11 ms	53596 KB	Output is correct
2	Correct	12 ms	53596 KB	Output is correct
3	Correct	11 ms	53576 KB	Output is correct
4	Correct	12 ms	54112 KB	Output is correct
5	Correct	13 ms	53852 KB	Output is correct
6	Correct	13 ms	53880 KB	Output is correct
7	Correct	11 ms	53728 KB	Output is correct
8	Correct	11 ms	53852 KB	Output is correct
9	Correct	11 ms	53756 KB	Output is correct
10	Correct	11 ms	53596 KB	Output is correct
11	Correct	11 ms	53816 KB	Output is correct
12	Correct	11 ms	53596 KB	Output is correct
13	Correct	12 ms	53596 KB	Output is correct
14	Correct	14 ms	53828 KB	Output is correct
15	Correct	11 ms	53852 KB	Output is correct
16	Correct	12 ms	53964 KB	Output is correct
17	Correct	11 ms	54072 KB	Output is correct
18	Correct	11 ms	54120 KB	Output is correct
19	Correct	15 ms	54108 KB	Output is correct
20	Correct	11 ms	54108 KB	Output is correct
21	Correct	13 ms	53984 KB	Output is correct
22	Correct	16 ms	54076 KB	Output is correct
23	Correct	12 ms	54092 KB	Output is correct
24	Correct	11 ms	54108 KB	Output is correct
25	Correct	11 ms	53860 KB	Output is correct
26	Correct	13 ms	53852 KB	Output is correct
27	Correct	12 ms	53852 KB	Output is correct
28	Correct	14 ms	53852 KB	Output is correct
29	Correct	16 ms	53852 KB	Output is correct
30	Correct	11 ms	53940 KB	Output is correct
31	Incorrect	17 ms	53852 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Submission #1045663

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