Submission #1140772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140772		Jawad_Akbar_JJ	Toy (CEOI24_toy)	C++20	0 / 100	102 ms	183880 KiB

Main

#include <iostream>
#include <queue>

using namespace std;
const int N = 1505;
int n, m, l, k, a[N][N], Seen[N][N];
vector<int> seen(46657000, 0);

int get(int i1, int j1, int i2, int j2){
	if (i1 > i2)
		swap(i1, i2);
	if (j1 > j2)
		swap(j1, j2);
	if (i1 == -1 or i2 == n or j1 == -1 or j2 == m) return 1;
	return a[i2][j2] - a[i1-1][j2] - a[i2][j1 - 1] + a[i1-1][j1-1];
}

int hsh(int xa, int ya, int xb, int yb){
	return xb * 360 + ya * 360 + (yb - ya);
}

queue<pair<pair<int,int>, pair<int,int>>> Q;
void push(int xa, int ya, int xb, int yb){
	if (xa + k - 1 < xb or xb < xa or yb > ya or ya + l - 1 < yb){
		// cout<<"done"<<endl;
		return;
	}
	int h = hsh(xa, ya, xb, yb);
	if (get(xa, ya, xa + k - 1, ya) + get(xb, yb, xb, yb + l - 1) == 0 and !seen[h]){
		Q.push({{xa, ya}, {xb, yb}});
		// cout<<xa<<" "<<ya<<" "<<xb<<" "<<yb<<'\n';
		seen[h] = 1;
		Seen[xb][ya] = 1;
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int xh, yh, xv, yv, x1, y1;
	cin>>n>>m>>k>>l; // k hor : l ver
	cin>>xh>>yh>>xv>>yv;

	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			char c;
			cin>>c;
			if (c == '*')
				x1 = i, y1 = j;
			a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + (c == '#');
		}
	}
	push(xh, yh, xv, yv);


	while (Q.size() > 0){
		auto [p1, p2] = Q.front();
		auto [xa, ya] = p1;
		auto [xb, yb] = p2;
		Q.pop();

		push(xa-1, ya, xb-1, yb);
		push(xa+1, ya, xb+1, yb);
		push(xa, ya-1, xb, yb-1);
		push(xa, ya+1, xb, yb+1);
		push(xa-1, ya, xb, yb);
		push(xa+1, ya, xb, yb);
		push(xa, ya, xb-1, yb);
		push(xa, ya, xb+1, yb);
		push(xa, ya-1, xb, yb);
		push(xa, ya+1, xb, yb);
		push(xa, ya, xb, yb-1);
		push(xa, ya, xb, yb+1);
	}

	if (Seen[x1][y1]){
		cout<<"YES\n";
	}
	else cout<<"NO\n";

}

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