oj.uz

Submission #258104

# Submission time Handle Problem Language Result Execution time Memory
258104 2020-08-05T11:11:34 Z sjimed Sandwich (JOI16_sandwich) C++14
35 / 100
 8000 ms 9720 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)

#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
string s[444];
int chk[444][444];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int t[2][2][2] = {
	1, 2,
	0, 3,
	2, 3,
	0, 1
};

int dir[2][4] = {
	1, 0, 0, 1,
	1, 1, 0, 0
};

int dfs(int x, int y, int d) {
	if(chk[x][y] == 1) return inf;
	if(chk[x][y] == 2) return 0;

	//cout << x << "!!! " << y << " " << d << endl;

	chk[x][y]=1;

	int ret = 2;

	for(int i=0; i<2; i++) {
		int nx = x + dx[t[s[x][y]][d][i]];
		int ny = y + dy[t[s[x][y]][d][i]];

		if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

		ret += dfs(nx, ny, dir[s[nx][ny]][t[s[x][y]][d][i]]);

		ret = min(inf, ret);
	}

	chk[x][y]=2;

	return ret;
}

int main() {
	fast;

	cin >> n >> m;

	for(int i=0; i<n; i++) {
		cin >> s[i];

		for(int j=0; j<m; j++) {
			if(s[i][j] == 'N') s[i][j] = 0;
			else s[i][j] = 1;
		}
	}

	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			memset(chk, 0, sizeof(chk));

			int ans = dfs(i, j, 0);
			
			memset(chk, 0, sizeof(chk));			
			ans = min(ans, dfs(i, j, 1));

			if(ans == inf) cout << -1 << " ";
			else cout << ans << " ";
		}

		cout << endl;
	}
}

Compilation message

sandwich.cpp: In function 'int dfs(int, int, int)':
sandwich.cpp:51:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   int nx = x + dx[t[s[x][y]][d][i]];
                            ^
sandwich.cpp:52:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   int ny = y + dy[t[s[x][y]][d][i]];
                            ^
sandwich.cpp:56:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   ret += dfs(nx, ny, dir[s[nx][ny]][t[s[x][y]][d][i]]);
                                   ^
sandwich.cpp:56:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   ret += dfs(nx, ny, dir[s[nx][ny]][t[s[x][y]][d][i]]);
                                              ^

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 15 ms 1152 KB Output is correct
6 Correct 540 ms 1400 KB Output is correct
7 Correct 220 ms 1272 KB Output is correct
8 Correct 240 ms 1152 KB Output is correct
9 Correct 179 ms 1272 KB Output is correct
10 Correct 267 ms 1272 KB Output is correct
11 Correct 288 ms 1272 KB Output is correct
12 Correct 121 ms 1152 KB Output is correct
13 Correct 312 ms 1272 KB Output is correct
14 Correct 318 ms 1212 KB Output is correct
15 Correct 190 ms 1188 KB Output is correct
16 Correct 175 ms 1272 KB Output is correct
17 Correct 174 ms 1152 KB Output is correct
18 Correct 179 ms 1184 KB Output is correct
19 Correct 192 ms 1152 KB Output is correct
20 Correct 204 ms 1152 KB Output is correct
21 Correct 210 ms 1152 KB Output is correct
22 Correct 190 ms 1272 KB Output is correct
23 Correct 192 ms 1152 KB Output is correct
24 Correct 350 ms 1152 KB Output is correct
25 Correct 349 ms 1152 KB Output is correct
26 Correct 342 ms 1400 KB Output is correct
27 Correct 262 ms 1272 KB Output is correct
28 Correct 324 ms 1152 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 15 ms 1152 KB Output is correct
6 Correct 540 ms 1400 KB Output is correct
7 Correct 220 ms 1272 KB Output is correct
8 Correct 240 ms 1152 KB Output is correct
9 Correct 179 ms 1272 KB Output is correct
10 Correct 267 ms 1272 KB Output is correct
11 Correct 288 ms 1272 KB Output is correct
12 Correct 121 ms 1152 KB Output is correct
13 Correct 312 ms 1272 KB Output is correct
14 Correct 318 ms 1212 KB Output is correct
15 Correct 190 ms 1188 KB Output is correct
16 Correct 175 ms 1272 KB Output is correct
17 Correct 174 ms 1152 KB Output is correct
18 Correct 179 ms 1184 KB Output is correct
19 Correct 192 ms 1152 KB Output is correct
20 Correct 204 ms 1152 KB Output is correct
21 Correct 210 ms 1152 KB Output is correct
22 Correct 190 ms 1272 KB Output is correct
23 Correct 192 ms 1152 KB Output is correct
24 Correct 350 ms 1152 KB Output is correct
25 Correct 349 ms 1152 KB Output is correct
26 Correct 342 ms 1400 KB Output is correct
27 Correct 262 ms 1272 KB Output is correct
28 Correct 324 ms 1152 KB Output is correct
29 Correct 23 ms 1152 KB Output is correct
30 Correct 23 ms 1152 KB Output is correct
31 Execution timed out 8041 ms 9720 KB Time limit exceeded
32 Halted 0 ms 0 KB -