Submission #1075581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075581		GrindMachine	Toy (CEOI24_toy)	C++17	0 / 100	1592 ms	936 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 = 1e5 + 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};

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];

	bool hok[n+5][m+5], vok[n+5][m+5];
	memset(hok,0,sizeof hok);
	memset(vok,0,sizeof vok);

	rep1(i,n){
		ll cnt = 0;
		rep1(j,w) cnt += a[i][j] == 'X';
		rep1(j,m){
			// can i place horiz here?
			if(j+w-1 > m) break;
			if(j > 1){
				cnt -= a[i][j-1] == 'X';
				cnt += a[i][j+w-1] == 'X';
			}

			if(cnt == 0){
				hok[i][j] = 1;
			}
		}
	}

	rep1(j,m){
		ll cnt = 0;
		rep1(i,h) cnt += a[i][j] == 'X';
		rep1(i,n){
			if(i+h-1 > n) break;
			if(i > 1){
				cnt -= a[i-1][j] == 'X';
				cnt += a[i+h-1][j] == 'X';
			}

			if(cnt == 0){
				vok[i][j] = 1;
			}
		}
	}

	bool vis1[n+5][m+5], vis2[n+5][m+5];
	memset(vis1,0,sizeof vis1);
	memset(vis2,0,sizeof vis2);

	{
		queue<pii> q;
		q.push({r1,c1});
		vis1[r1][c1] = 1;
		while(!q.empty()){
			auto [i,j] = q.front();
			q.pop();

			rep(x,4){
				int i2 = i+dx[x], j2 = j+dy[x];
				if(!hok[i2][j2]) conts;
				if(vis1[i2][j2]) conts;
				vis1[i2][j2] = 1;
				q.push({i2,j2});
			}
		}
	}

	{
		queue<pii> q;
		q.push({r2,c2});
		vis2[r2][c2] = 1;
		while(!q.empty()){
			auto [i,j] = q.front();
			q.pop();

			rep(x,4){
				int i2 = i+dx[x], j2 = j+dy[x];
				if(!vok[i2][j2]) conts;
				if(vis2[i2][j2]) conts;
				vis2[i2][j2] = 1;
				q.push({i2,j2});
			}
		}
	}

	rep1(i1,n){
		rep1(j1,m){
			rep1(i2,n){
				rep1(j2,m){
					if(vis1[i1][j1] and vis2[i2][j2]){

					}
					else{
						conts;
					}

					ll ok = 0;
					if(j1 <= j2 and j2 <= j1+w-1){
						ok++;
					}
					if(i2 <= i1 and i1 <= i2+h-1){
						ok++;
					}
					if(a[i1][j2] == '*'){
						ok++;
					}

					// if(i1 == 1 and j1 == 3 and i2 == 1 and j2 == 4){
					// 	debug(ok);
					// }

					if(ok == 3){
						// vector<ll> v = {i1,j1,i2,j2};
						// debug(v);
						yes;
						return;
					} 
				}
			}
		}
	}

	no;
} 

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

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

	return 0;
}

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