oj.uz

Submission #1075581

# Submission time Handle Problem Language Result Execution time Memory
1075581 2024-08-26T07:49:54 Z GrindMachine Toy (CEOI24_toy) C++17
0 / 100
 1500 ms 936 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4 ms 444 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 7 ms 444 KB Output is correct
11 Correct 6 ms 448 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 8 ms 440 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Incorrect 2 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4 ms 444 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 7 ms 444 KB Output is correct
11 Correct 6 ms 448 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 8 ms 440 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Incorrect 2 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 7 ms 348 KB Output is correct
4 Execution timed out 1592 ms 936 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4 ms 444 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 7 ms 444 KB Output is correct
11 Correct 6 ms 448 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 8 ms 440 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Incorrect 2 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4 ms 444 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 7 ms 444 KB Output is correct
11 Correct 6 ms 448 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 8 ms 440 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Incorrect 2 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -