Submission #1193387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193387		JooDdae	Sandwich (JOI16_sandwich)	C++20	0 / 100	0 ms	1096 KiB

sandwich

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

const int INF = 1e9;

int n, m, d[808][808], p[808][808];
string s[404];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i=0;i<n;i++) cin >> s[i];

	for(int i=0;i<n+n;i++) fill(d[i], d[i]+m+m, INF);
	for(int i=0;i<n+n;i++) for(int j=0;j<m+m;j++) p[i][j] = (i != 0 && i != n+n-1) + (j != 0 && j != m+m-1);

	queue<array<int, 3>> q;
	if(s[0][0] == 'Z') q.push({1, 0, 0}), d[0][0] = 1;
	if(s[n-1][0] == 'N') q.push({1, 2*n-1, 0}), d[2*n-1][0] = 1;
	if(s[0][m-1] == 'N') q.push({1, 0, 2*m-1}), d[0][2*m-1] = 1;
	if(s[n-1][m-1] == 'Z') q.push({1, 2*n-1, 2*m-1}), d[2*n-1][2*m-1] = 1;

	while(!q.empty()) {
		auto [c, x, y] = q.front(); q.pop();

		if(d[x^1][y^1] == INF) {
			q.push({c+1, x^1, y^1}), d[x^1][y^1] = c+1;
		}

		int xx = x + ((x & 1) ? 1 : -1), yy = y + ((y & 1 ? 1 : -1));

		if(0 <= xx && xx < n+n) {
			int yy = y ^ (s[x/2][y/2] == s[xx/2][y/2]);
			if(d[xx][yy] == INF && !--p[xx][yy]) {
				q.push({c+1, xx, yy}), d[xx][yy] = c+1;
			}
		}
		if(0 <= yy && yy < m+m) {
			int xx = x ^ (s[x/2][y/2] == s[x/2][yy/2]);
			if(d[xx][yy] == INF && !--p[xx][yy]) {
				q.push({c+1, xx, yy}), d[xx][yy] = c+1;
			}
		}
	}

	for(int i=0;i<n+n;i+=2) {
		for(int j=0;j<m+m;j+=2) {
			auto u = min(d[i ^ (s[i/2][j/2] == 'N')][j], d[i ^ (s[i/2][j/2] == 'Z')][j^1]);
			cout << (u == INF ? -1 : u+1) << " ";
		}
		cout << "\n";
	}
}

• Subtask 1: 0 / 35
• Subtask 2: 0 / 65