Submission #590126

#	Time	Username	Problem	Language	Result	Execution time	Memory
590126		dutinmeow	Sandwich (JOI16_sandwich)	C++17	100 / 100	1987 ms	2644 KiB

sandwich

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

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

const int INF = 1e9;
const array<int, 4> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<char>> A(N + 2, vector<char>(M + 2));
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> A[i][j];

	int time = 0;
	vector<vector<bool>> vis(N + 2, vector<bool>(M + 2, false)), inq(N + 2, vector<bool>(M + 2, false));

	auto dfs = y_combinator([&](auto dfs, int x, int y, int t) -> void {
		if (time >= INF || inq[x][y]) 
			return void(time = INF);
		if (x <= 0 || x > N || y <= 0 || y > M || vis[x][y])
			return;
		vis[x][y] = inq[x][y] = true;
		time++;
		dfs(x + dx[t], y + dy[t], t);
		if (A[x][y] == 'Z') {
			int s = (t ^ 1);
			dfs(x + dx[s], y + dy[s], s);
		} else {
			int s = (t ^ 1 ^ 2);
			dfs(x + dx[s], y + dy[s], s);
		}
		inq[x][y] = false;
	});
	
	vector<vector<int>> ans(N + 2, vector<int>(M + 2, INF));
	for (int t : {1, 3}) {
		for (int i = N; i >= 1; i--) {
			for (int j = 1; j <= N; j++) {
				fill(vis[j].begin(), vis[j].end(), false);
				fill(inq[j].begin(), inq[j].end(), false);
			}
			time = 0;
			if (t == 3) {
				for (int j = 1; j <= M; j++) {
					dfs(i, j, t);
					ans[i][j] = min(ans[i][j], time);
				}
			} else {
				for (int j = M; j >= 1; j--) {
					dfs(i, j, t);
					ans[i][j] = min(ans[i][j], time);
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) 
		for (int j = 1; j <= M; j++) 
			cout << (ans[i][j] >= INF ? -1 : ans[i][j] * 2) << " \n"[j == M];
}

Compilation message (stderr)

sandwich.cpp:4: warning: ignoring '#pragma region y_combinator' [-Wunknown-pragmas]
    4 | #pragma region y_combinator
      | 
sandwich.cpp:29: warning: ignoring '#pragma endregion y_combinator' [-Wunknown-pragmas]
   29 | #pragma endregion y_combinator
      |

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