Submission #1126451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126451		Matthewwww	Sandwich (JOI16_sandwich)	C++17	35 / 100	3781 ms	11384 KiB

sandwich

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define err cout
#else
#define err if(0) cout
#endif
 
//0 is up, 1 is down, 2 is left (from)
 
void dfs (int i, int j, int dir, vector<vector<int>> &been, int &num, vector<string> &grid){
	if (grid[i][j] == 'Z')
		dir %= 2;
	else
		dir = min(dir, 3-dir);
	if (been[i][j]){
		if (been[i][j]-1 != dir)
			num = 320000;
		return;
	}
	been[i][j] = dir+1;
	num++;
	if (dir){
		if (grid[i][j] == 'Z'){
			if (i)
				dfs(i-1, j, 1, been, num, grid);
			if (j)
				dfs(i, j-1, 3, been, num, grid);
		} else {
			if (j+1 < (int)grid[0].size())
				dfs(i, j+1, 2, been, num, grid);
			if (i)
				dfs(i-1, j, 1, been, num, grid);
		}
	} else {
		if (grid[i][j] == 'Z'){
			if (i+1 < (int)grid.size())
				dfs(i+1, j, 0, been, num, grid);
			if (j+1 < (int)grid[0].size())
				dfs(i, j+1, 2, been, num, grid);
		}
		else {
			if (i+1 < (int)grid.size())
				dfs(i+1, j, 0, been, num, grid);
			if (j)
				dfs(i, j-1, 3, been, num, grid);
		}
	}
	//err << i << " " << j << " " << dir << " " << ret << "\n";
	//return ret;
}
 
const int dir[5] = {1, 0, -1, 0, 1};
	
vector<vector<bool>> poss (int n, int m, vector<string> grid){
	vector<vector<bool>> up(n, vector<bool>(m, 1));
	vector<vector<bool>> down = up, right = up, left = up;
	for (int i = 0; i < m; i++)
		up[0][i] = down[n-1][i] = 0;
	for (int i = 0; i < n; i++)
		left[i][0] = right[i][m-1] = 0;
	queue<pair<int, int>> q;
#define check(i, j) (grid[i][j] == 'N' ? (!up[i][j] && !right[i][j]) || (!left[i][j] && !down[i][j]) : (!up[i][j] && !left[i][j]) || (!down[i][j] && !right[i][j]))
	vector<vector<int>> ans(n, vector<int>(m, -1));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (check(i, j))
				q.push({i, j});
	q.push({-1, -1});
	int d = 1;
	while (~q.front().f){
		while (~q.front().f){
			int x = q.front().f, y = q.front().s;
			q.pop();
			if (!~ans[x][y]){
				ans[x][y] = d;
				for (int i = 0; i < 4; i++){
					if (x+dir[i] >= 0 && x+dir[i] < n && y+dir[i+1] >= 0 && y+dir[i+1] < m){
						if (i == 0)
							up[x+dir[i]][y+dir[i+1]] = 0;
						if (i == 1)
							right[x+dir[i]][y+dir[i+1]] = 0;
						if (i == 2)
							down[x+dir[i]][y+dir[i+1]] = 0;
						if (i == 3)
							left[x+dir[i]][y+dir[i+1]] = 0;
						if (check(x+dir[i], y+dir[i+1]))
							q.push({x+dir[i], y+dir[i+1]});
					}
				}
			}
		}
		q.pop();
		q.push({-1, -1});
		d++;
	}
	vector<vector<bool>> p(n, vector<bool>(m, 0));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			p[i][j] = ~ans[i][j];
	return p;
}
 
vector<vector<int>> solve(int n, int m, vector<string> grid){
	vector<vector<int>> ans(n, vector<int>(m, INT_MAX));
	for (int i = 0; i < m; i++){
		vector<vector<int>> been(n, vector<int>(m, 0));
		int num = 0;
		for (int j = 0; j < n; j++){
			dfs(j, i, 1, been, num, grid);
			if (num > 300000)
				break;
			ans[j][i] = num;
		}
	}
	return ans;
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<string> grid(n);
	for (auto &i : grid)
		cin >> i;
	auto hehe = poss(n, m, grid);
	auto ret = solve(n, m, grid);
	reverse(grid.begin(), grid.end());
	for (auto &i : grid)
		reverse(i.begin(), i.end());
	auto r2 = solve(n, m, grid);
	for (auto &i : r2)
		reverse(i.begin(), i.end());
	reverse(r2.begin(), r2.end());
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++)
			cout << (hehe[i][j]&&(min(ret[i][j], r2[i][j]) <= 300000) ? min(ret[i][j], r2[i][j])*2 : -1ll) << " ";
		cout << "\n";
	}
}

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