oj.uz

Submission #1045633

# Submission time Handle Problem Language Result Execution time Memory
1045633 2024-08-06T06:38:57 Z Tsovak Toy (CEOI24_toy) C++17
0 / 100
 25 ms 66528 KB 
// -------------------- 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) {
				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) {
				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 8 ms 55732 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 8 ms 55732 KB Output is correct
3 Correct 8 ms 55896 KB Output is correct
4 Correct 9 ms 56156 KB Output is correct
5 Correct 8 ms 55900 KB Output is correct
6 Correct 7 ms 55896 KB Output is correct
7 Correct 8 ms 55956 KB Output is correct
8 Correct 8 ms 55900 KB Output is correct
9 Correct 8 ms 55644 KB Output is correct
10 Correct 8 ms 55752 KB Output is correct
11 Correct 9 ms 55800 KB Output is correct
12 Correct 8 ms 55644 KB Output is correct
13 Correct 8 ms 55640 KB Output is correct
14 Correct 8 ms 55776 KB Output is correct
15 Correct 8 ms 55992 KB Output is correct
16 Correct 8 ms 55900 KB Output is correct
17 Correct 7 ms 55900 KB Output is correct
18 Correct 7 ms 56156 KB Output is correct
19 Correct 7 ms 56172 KB Output is correct
20 Correct 8 ms 56156 KB Output is correct
21 Correct 7 ms 56040 KB Output is correct
22 Correct 8 ms 56156 KB Output is correct
23 Correct 8 ms 56156 KB Output is correct
24 Correct 7 ms 56168 KB Output is correct
25 Correct 7 ms 56156 KB Output is correct
26 Correct 8 ms 55900 KB Output is correct
27 Correct 8 ms 55900 KB Output is correct
28 Correct 8 ms 55900 KB Output is correct
29 Correct 7 ms 56020 KB Output is correct
30 Correct 7 ms 56152 KB Output is correct
31 Incorrect 8 ms 56000 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 8 ms 55732 KB Output is correct
3 Correct 8 ms 55896 KB Output is correct
4 Correct 9 ms 56156 KB Output is correct
5 Correct 8 ms 55900 KB Output is correct
6 Correct 7 ms 55896 KB Output is correct
7 Correct 8 ms 55956 KB Output is correct
8 Correct 8 ms 55900 KB Output is correct
9 Correct 8 ms 55644 KB Output is correct
10 Correct 8 ms 55752 KB Output is correct
11 Correct 9 ms 55800 KB Output is correct
12 Correct 8 ms 55644 KB Output is correct
13 Correct 8 ms 55640 KB Output is correct
14 Correct 8 ms 55776 KB Output is correct
15 Correct 8 ms 55992 KB Output is correct
16 Correct 8 ms 55900 KB Output is correct
17 Correct 7 ms 55900 KB Output is correct
18 Correct 7 ms 56156 KB Output is correct
19 Correct 7 ms 56172 KB Output is correct
20 Correct 8 ms 56156 KB Output is correct
21 Correct 7 ms 56040 KB Output is correct
22 Correct 8 ms 56156 KB Output is correct
23 Correct 8 ms 56156 KB Output is correct
24 Correct 7 ms 56168 KB Output is correct
25 Correct 7 ms 56156 KB Output is correct
26 Correct 8 ms 55900 KB Output is correct
27 Correct 8 ms 55900 KB Output is correct
28 Correct 8 ms 55900 KB Output is correct
29 Correct 7 ms 56020 KB Output is correct
30 Correct 7 ms 56152 KB Output is correct
31 Incorrect 8 ms 56000 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 8 ms 55732 KB Output is correct
3 Correct 9 ms 56156 KB Output is correct
4 Correct 19 ms 66232 KB Output is correct
5 Correct 20 ms 66396 KB Output is correct
6 Correct 9 ms 58796 KB Output is correct
7 Correct 21 ms 65116 KB Output is correct
8 Correct 21 ms 65500 KB Output is correct
9 Correct 11 ms 58712 KB Output is correct
10 Correct 18 ms 60836 KB Output is correct
11 Correct 17 ms 59740 KB Output is correct
12 Correct 9 ms 57948 KB Output is correct
13 Correct 12 ms 58204 KB Output is correct
14 Correct 12 ms 58204 KB Output is correct
15 Correct 18 ms 65860 KB Output is correct
16 Correct 18 ms 65624 KB Output is correct
17 Correct 18 ms 65628 KB Output is correct
18 Correct 21 ms 66396 KB Output is correct
19 Correct 19 ms 66436 KB Output is correct
20 Correct 19 ms 66396 KB Output is correct
21 Correct 20 ms 66396 KB Output is correct
22 Correct 20 ms 66392 KB Output is correct
23 Correct 19 ms 66396 KB Output is correct
24 Correct 20 ms 66528 KB Output is correct
25 Correct 19 ms 66512 KB Output is correct
26 Correct 18 ms 64856 KB Output is correct
27 Correct 18 ms 64860 KB Output is correct
28 Correct 18 ms 64844 KB Output is correct
29 Correct 22 ms 64860 KB Output is correct
30 Correct 25 ms 66184 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 8 ms 55732 KB Output is correct
3 Correct 8 ms 55896 KB Output is correct
4 Correct 9 ms 56156 KB Output is correct
5 Correct 8 ms 55900 KB Output is correct
6 Correct 7 ms 55896 KB Output is correct
7 Correct 8 ms 55956 KB Output is correct
8 Correct 8 ms 55900 KB Output is correct
9 Correct 8 ms 55644 KB Output is correct
10 Correct 8 ms 55752 KB Output is correct
11 Correct 9 ms 55800 KB Output is correct
12 Correct 8 ms 55644 KB Output is correct
13 Correct 8 ms 55640 KB Output is correct
14 Correct 8 ms 55776 KB Output is correct
15 Correct 8 ms 55992 KB Output is correct
16 Correct 8 ms 55900 KB Output is correct
17 Correct 7 ms 55900 KB Output is correct
18 Correct 7 ms 56156 KB Output is correct
19 Correct 7 ms 56172 KB Output is correct
20 Correct 8 ms 56156 KB Output is correct
21 Correct 7 ms 56040 KB Output is correct
22 Correct 8 ms 56156 KB Output is correct
23 Correct 8 ms 56156 KB Output is correct
24 Correct 7 ms 56168 KB Output is correct
25 Correct 7 ms 56156 KB Output is correct
26 Correct 8 ms 55900 KB Output is correct
27 Correct 8 ms 55900 KB Output is correct
28 Correct 8 ms 55900 KB Output is correct
29 Correct 7 ms 56020 KB Output is correct
30 Correct 7 ms 56152 KB Output is correct
31 Incorrect 8 ms 56000 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 8 ms 55732 KB Output is correct
3 Correct 8 ms 55896 KB Output is correct
4 Correct 9 ms 56156 KB Output is correct
5 Correct 8 ms 55900 KB Output is correct
6 Correct 7 ms 55896 KB Output is correct
7 Correct 8 ms 55956 KB Output is correct
8 Correct 8 ms 55900 KB Output is correct
9 Correct 8 ms 55644 KB Output is correct
10 Correct 8 ms 55752 KB Output is correct
11 Correct 9 ms 55800 KB Output is correct
12 Correct 8 ms 55644 KB Output is correct
13 Correct 8 ms 55640 KB Output is correct
14 Correct 8 ms 55776 KB Output is correct
15 Correct 8 ms 55992 KB Output is correct
16 Correct 8 ms 55900 KB Output is correct
17 Correct 7 ms 55900 KB Output is correct
18 Correct 7 ms 56156 KB Output is correct
19 Correct 7 ms 56172 KB Output is correct
20 Correct 8 ms 56156 KB Output is correct
21 Correct 7 ms 56040 KB Output is correct
22 Correct 8 ms 56156 KB Output is correct
23 Correct 8 ms 56156 KB Output is correct
24 Correct 7 ms 56168 KB Output is correct
25 Correct 7 ms 56156 KB Output is correct
26 Correct 8 ms 55900 KB Output is correct
27 Correct 8 ms 55900 KB Output is correct
28 Correct 8 ms 55900 KB Output is correct
29 Correct 7 ms 56020 KB Output is correct
30 Correct 7 ms 56152 KB Output is correct
31 Incorrect 8 ms 56000 KB Output isn't correct
32 Halted 0 ms 0 KB -