oj.uz

답안 #1045658

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1045658 2024-08-06T06:48:06 Z Tsovak Toy (CEOI24_toy) C++17
0 / 100
 35 ms 66536 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 && 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 55644 KB Output is correct
2 Correct 7 ms 55644 KB Output is correct
3 Correct 7 ms 55900 KB Output is correct
4 Correct 7 ms 56016 KB Output is correct
5 Correct 7 ms 56044 KB Output is correct
6 Correct 7 ms 55896 KB Output is correct
7 Correct 8 ms 55900 KB Output is correct
8 Correct 7 ms 55900 KB Output is correct
9 Correct 7 ms 55644 KB Output is correct
10 Correct 8 ms 55644 KB Output is correct
11 Correct 7 ms 55872 KB Output is correct
12 Correct 8 ms 55788 KB Output is correct
13 Correct 9 ms 56024 KB Output is correct
14 Correct 8 ms 55876 KB Output is correct
15 Correct 8 ms 56156 KB Output is correct
16 Correct 7 ms 56108 KB Output is correct
17 Correct 8 ms 55900 KB Output is correct
18 Correct 8 ms 56064 KB Output is correct
19 Correct 8 ms 56032 KB Output is correct
20 Correct 7 ms 56156 KB Output is correct
21 Correct 9 ms 55996 KB Output is correct
22 Correct 7 ms 56156 KB Output is correct
23 Correct 11 ms 56156 KB Output is correct
24 Correct 7 ms 56156 KB Output is correct
25 Correct 8 ms 56156 KB Output is correct
26 Correct 8 ms 56072 KB Output is correct
27 Correct 7 ms 55900 KB Output is correct
28 Correct 8 ms 56152 KB Output is correct
29 Correct 8 ms 56128 KB Output is correct
30 Correct 9 ms 56156 KB Output is correct
31 Incorrect 8 ms 55900 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 55644 KB Output is correct
2 Correct 7 ms 55644 KB Output is correct
3 Correct 7 ms 55900 KB Output is correct
4 Correct 7 ms 56016 KB Output is correct
5 Correct 7 ms 56044 KB Output is correct
6 Correct 7 ms 55896 KB Output is correct
7 Correct 8 ms 55900 KB Output is correct
8 Correct 7 ms 55900 KB Output is correct
9 Correct 7 ms 55644 KB Output is correct
10 Correct 8 ms 55644 KB Output is correct
11 Correct 7 ms 55872 KB Output is correct
12 Correct 8 ms 55788 KB Output is correct
13 Correct 9 ms 56024 KB Output is correct
14 Correct 8 ms 55876 KB Output is correct
15 Correct 8 ms 56156 KB Output is correct
16 Correct 7 ms 56108 KB Output is correct
17 Correct 8 ms 55900 KB Output is correct
18 Correct 8 ms 56064 KB Output is correct
19 Correct 8 ms 56032 KB Output is correct
20 Correct 7 ms 56156 KB Output is correct
21 Correct 9 ms 55996 KB Output is correct
22 Correct 7 ms 56156 KB Output is correct
23 Correct 11 ms 56156 KB Output is correct
24 Correct 7 ms 56156 KB Output is correct
25 Correct 8 ms 56156 KB Output is correct
26 Correct 8 ms 56072 KB Output is correct
27 Correct 7 ms 55900 KB Output is correct
28 Correct 8 ms 56152 KB Output is correct
29 Correct 8 ms 56128 KB Output is correct
30 Correct 9 ms 56156 KB Output is correct
31 Incorrect 8 ms 55900 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 55644 KB Output is correct
2 Correct 7 ms 55644 KB Output is correct
3 Correct 9 ms 56156 KB Output is correct
4 Correct 20 ms 66396 KB Output is correct
5 Correct 25 ms 66472 KB Output is correct
6 Correct 10 ms 58972 KB Output is correct
7 Correct 26 ms 65100 KB Output is correct
8 Correct 23 ms 65628 KB Output is correct
9 Correct 11 ms 58608 KB Output is correct
10 Correct 18 ms 60992 KB Output is correct
11 Correct 24 ms 59636 KB Output is correct
12 Correct 9 ms 57948 KB Output is correct
13 Correct 13 ms 58204 KB Output is correct
14 Correct 13 ms 58108 KB Output is correct
15 Correct 34 ms 65880 KB Output is correct
16 Correct 23 ms 65628 KB Output is correct
17 Correct 22 ms 65400 KB Output is correct
18 Correct 35 ms 66388 KB Output is correct
19 Correct 24 ms 66392 KB Output is correct
20 Correct 21 ms 66396 KB Output is correct
21 Correct 22 ms 66484 KB Output is correct
22 Correct 23 ms 66384 KB Output is correct
23 Correct 23 ms 66316 KB Output is correct
24 Correct 22 ms 66536 KB Output is correct
25 Correct 24 ms 66496 KB Output is correct
26 Correct 26 ms 64820 KB Output is correct
27 Correct 22 ms 64756 KB Output is correct
28 Correct 23 ms 64860 KB Output is correct
29 Correct 28 ms 64900 KB Output is correct
30 Correct 23 ms 66004 KB Output is correct
31 Incorrect 21 ms 65884 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 55644 KB Output is correct
2 Correct 7 ms 55644 KB Output is correct
3 Correct 7 ms 55900 KB Output is correct
4 Correct 7 ms 56016 KB Output is correct
5 Correct 7 ms 56044 KB Output is correct
6 Correct 7 ms 55896 KB Output is correct
7 Correct 8 ms 55900 KB Output is correct
8 Correct 7 ms 55900 KB Output is correct
9 Correct 7 ms 55644 KB Output is correct
10 Correct 8 ms 55644 KB Output is correct
11 Correct 7 ms 55872 KB Output is correct
12 Correct 8 ms 55788 KB Output is correct
13 Correct 9 ms 56024 KB Output is correct
14 Correct 8 ms 55876 KB Output is correct
15 Correct 8 ms 56156 KB Output is correct
16 Correct 7 ms 56108 KB Output is correct
17 Correct 8 ms 55900 KB Output is correct
18 Correct 8 ms 56064 KB Output is correct
19 Correct 8 ms 56032 KB Output is correct
20 Correct 7 ms 56156 KB Output is correct
21 Correct 9 ms 55996 KB Output is correct
22 Correct 7 ms 56156 KB Output is correct
23 Correct 11 ms 56156 KB Output is correct
24 Correct 7 ms 56156 KB Output is correct
25 Correct 8 ms 56156 KB Output is correct
26 Correct 8 ms 56072 KB Output is correct
27 Correct 7 ms 55900 KB Output is correct
28 Correct 8 ms 56152 KB Output is correct
29 Correct 8 ms 56128 KB Output is correct
30 Correct 9 ms 56156 KB Output is correct
31 Incorrect 8 ms 55900 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 55644 KB Output is correct
2 Correct 7 ms 55644 KB Output is correct
3 Correct 7 ms 55900 KB Output is correct
4 Correct 7 ms 56016 KB Output is correct
5 Correct 7 ms 56044 KB Output is correct
6 Correct 7 ms 55896 KB Output is correct
7 Correct 8 ms 55900 KB Output is correct
8 Correct 7 ms 55900 KB Output is correct
9 Correct 7 ms 55644 KB Output is correct
10 Correct 8 ms 55644 KB Output is correct
11 Correct 7 ms 55872 KB Output is correct
12 Correct 8 ms 55788 KB Output is correct
13 Correct 9 ms 56024 KB Output is correct
14 Correct 8 ms 55876 KB Output is correct
15 Correct 8 ms 56156 KB Output is correct
16 Correct 7 ms 56108 KB Output is correct
17 Correct 8 ms 55900 KB Output is correct
18 Correct 8 ms 56064 KB Output is correct
19 Correct 8 ms 56032 KB Output is correct
20 Correct 7 ms 56156 KB Output is correct
21 Correct 9 ms 55996 KB Output is correct
22 Correct 7 ms 56156 KB Output is correct
23 Correct 11 ms 56156 KB Output is correct
24 Correct 7 ms 56156 KB Output is correct
25 Correct 8 ms 56156 KB Output is correct
26 Correct 8 ms 56072 KB Output is correct
27 Correct 7 ms 55900 KB Output is correct
28 Correct 8 ms 56152 KB Output is correct
29 Correct 8 ms 56128 KB Output is correct
30 Correct 9 ms 56156 KB Output is correct
31 Incorrect 8 ms 55900 KB Output isn't correct
32 Halted 0 ms 0 KB -