Submission #1075644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075644		GrindMachine	Toy (CEOI24_toy)	C++17	100 / 100	191 ms	77832 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define conts continue
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(a) (int)a.size()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i) 
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
	x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
	x = max(x,y);
}

template<typename A,typename B>
string to_string(pair<A,B> p);

string to_string(const string &s){
	return "'"+s+"'";
}

string to_string(const char *s){
	return to_string((string)s);
}

string to_string(bool b){
	return b?"true":"false";
}

template<typename A>
string to_string(A v){
	string res = "{";
	trav(x,v){
		res += to_string(x)+",";
	}
	if(res.back() == ',') res.pop_back();
	res += "}";
	return res;
}

template<typename A,typename B>
string to_string(pair<A,B> p){
	return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}

#define debug(x) cout << #x << " = "; cout << to_string(x) << endl

const int MOD = 1e9 + 7;
const int N = 1.5e3 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

vector<int> dx = {-1,1,0,0};
vector<int> dy = {0,0,-1,1};

int cu[N][N], cd[N][N], cl[N][N], cr[N][N];
pii hr[N][N], vr[N][N];
bool vis[N][N];

void solve(int test_case){
	int m,n,w,h; cin >> m >> n >> w >> h;
	int c1,r1,c2,r2; cin >> c1 >> r1 >> c2 >> r2;
	c1++, r1++, c2++, r2++;
	char a[n+5][m+5];
	rep1(i,n) rep1(j,m) cin >> a[i][j];

	rep1(i,n){
		int c = 0;
		rep1(j,m){
			if(a[i][j] == 'X') c = j;
			cl[i][j] = c;
		}
		c = m+1;
		rev(j,m,1){
			if(a[i][j] == 'X') c = j;
			cr[i][j] = c;
		}
	}

	rep1(j,m){
		int c = 0;
		rep1(i,n){
			if(a[i][j] == 'X') c = i;
			cu[i][j] = c;
		}
		c = n+1;
		rev(i,n,1){
			if(a[i][j] == 'X') c = i;
			cd[i][j] = c;
		}
	}

	rep1(i,n){
		rep1(j,m){
			if(a[i][j] == 'X') conts;
			int l = cl[i][j], r = cr[i][j];
			l++, r--;
			int lx = max(j-w+1,l);
			int rx = min(j,r-w+1);
			hr[i][j] = {lx,rx};
		}
	}

	rep1(i,n){
		rep1(j,m){
			if(a[i][j] == 'X') conts;
			int l = cu[i][j], r = cd[i][j];
			l++, r--;
			int lx = max(i-h+1,l);
			int rx = min(i,r-h+1);
			vr[i][j] = {lx,rx};
		}
	}

	auto f = [&](pii p1, pii p2){
		auto [l1,r1] = p1;
		auto [l2,r2] = p2;
		if(l1 > r1 or l2 > r2) return false;
		return max(l1,l2) <= min(r1,r2);
	};

	queue<pii> q;
	q.push({r1,c2});
	vis[r1][c2] = 1;

	while(!q.empty()){
		auto [i,j] = q.front();
		q.pop();

		if(a[i][j] == '*'){
			yes;
			return;
		}

		rep(dir,4){
			int i2 = i+dx[dir], j2 = j+dy[dir];
			if(i2 < 1 or i2 > n or j2 < 1 or j2 > m) conts;
			if(vis[i2][j2]) conts;

			bool ok = false;

			if(dir >= 2){
				if(dir == 2){
					// L
					if(j > hr[i][j].ff){
						ok = f(vr[i][j],vr[i][j-1]);
					}
				}
				else{
					// R
					if(j < hr[i][j].ss+w-1){
						ok = f(vr[i][j],vr[i][j+1]);
					}
				}
			}
			else{
				if(dir == 0){
					// U
					if(i > vr[i][j].ff){
						ok = f(hr[i][j],hr[i-1][j]);
					}
				}
				else{
					// D
					if(i < vr[i][j].ss+h-1){
						ok = f(hr[i][j],hr[i+1][j]);
					}
				}
			}

			if(!ok) conts;

			vis[i2][j2] = 1;
			q.push({i2,j2});
		}
	}

	no;
} 

int main(){
	int t = 1;
	// cin >> t;

	rep1(i,t){
		solve(i);
	}

	return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27