oj.uz

Submission #876661

# Submission time Handle Problem Language Result Execution time Memory
876661 2023-11-22T07:49:28 Z MisterReaper Mecho (IOI09_mecho) C++17
57 / 100
 1000 ms 7764 KB 
#pragma optimize("unroll-loops,O3")

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

const int MAXN = 800 + 5;

char matrix[MAXN][MAXN];
int distBee[MAXN][MAXN];
int distBear[MAXN][MAXN];

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

#define ONLINE_JUDGE
void solve() {
	memset(distBee, -1, sizeof(distBee));

	int n, s;
	cin >> n >> s;

	pair <int, int> initial;
	pair <int, int> home;

	queue <array <int, 3>> q;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> matrix[i][j];
			if(matrix[i][j] == 'H') {
				q.push({0, i, j});
			} else if(matrix[i][j] == 'M') {
				initial = {i, j};
			} else if(matrix[i][j] == 'D') {
				home = {i, j};
			}
		}
	}

	auto in = [&](int x, int y) -> bool {
		return 1 <= min(x, y) && max(x, y) <= n;
	};

	while(!q.empty()) {
		auto [d, x, y] = q.front();
		q.pop();
		if(distBee[x][y] != -1) {
			continue;
		}

		distBee[x][y] = d;
		for(int dir = 0; dir < 4; dir++) {
			int _x = x + dx[dir], _y = y + dy[dir];
			if(in(_x, _y) && matrix[_x][_y] == 'G') {
				q.push({d +1, _x, _y});
			}
		}
	}

	for(int ans = 0; ; ans++) {
		memset(distBear, -1, sizeof(distBear));

		q.push({s * ans, initial.first, initial.second});
		while(!q.empty()) {
			auto [d, x, y] = q.front();
			q.pop();
			if(distBear[x][y] != -1 || (distBee[x][y] != -1 && d / s >= distBee[x][y])) {
				continue;
			}

			//cerr << d << " :: " << x << " " << y << " | " << distBee[x][y] << "\n";
			distBear[x][y] = d;
			for(int dir = 0; dir < 4; dir++) {
				int _x = x + dx[dir], _y = y + dy[dir];
				if(in(_x, _y) && (matrix[_x][_y] == 'G' || matrix[_x][_y] == 'D') && distBear[_x][_y] == -1) {
					q.push({d +1, _x, _y});
				}
			}
		}

		if(distBear[home.first][home.second] == -1) {
			cout << ans -1;
			return;
		}

		//cerr << "\n";
	}
	
	return;
}

signed main() {
	#ifndef ONLINE_JUDGE
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int t = 1; //cin >> t;
	for(int i = 1; i <= t; i++) {
		solve();
	}

	return 0;
}

Compilation message

mecho.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("unroll-loops,O3")
      |

Subtask #1
57.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5468 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 1 ms 5468 KB Output is correct
4 Correct 1 ms 5468 KB Output is correct
5 Correct 1 ms 5468 KB Output is correct
6 Correct 1 ms 5532 KB Output is correct
7 Correct 227 ms 6788 KB Output is correct
8 Correct 1 ms 5464 KB Output is correct
9 Correct 2 ms 5468 KB Output is correct
10 Correct 1 ms 5468 KB Output is correct
11 Correct 1 ms 5464 KB Output is correct
12 Execution timed out 1074 ms 5468 KB Time limit exceeded
13 Incorrect 1 ms 5464 KB Output isn't correct
14 Correct 1 ms 5468 KB Output is correct
15 Correct 8 ms 5468 KB Output is correct
16 Correct 4 ms 5468 KB Output is correct
17 Correct 12 ms 5552 KB Output is correct
18 Correct 6 ms 5480 KB Output is correct
19 Correct 18 ms 5468 KB Output is correct
20 Correct 9 ms 5464 KB Output is correct
21 Correct 32 ms 5556 KB Output is correct
22 Correct 18 ms 5468 KB Output is correct
23 Correct 54 ms 5468 KB Output is correct
24 Correct 28 ms 5468 KB Output is correct
25 Correct 84 ms 5468 KB Output is correct
26 Correct 48 ms 5464 KB Output is correct
27 Correct 102 ms 5564 KB Output is correct
28 Correct 60 ms 5564 KB Output is correct
29 Correct 125 ms 5480 KB Output is correct
30 Correct 68 ms 5564 KB Output is correct
31 Correct 143 ms 5712 KB Output is correct
32 Correct 81 ms 5468 KB Output is correct
33 Execution timed out 1067 ms 5724 KB Time limit exceeded
34 Execution timed out 1059 ms 5720 KB Time limit exceeded
35 Correct 23 ms 5724 KB Output is correct
36 Execution timed out 1055 ms 5724 KB Time limit exceeded
37 Execution timed out 1051 ms 5720 KB Time limit exceeded
38 Correct 22 ms 5724 KB Output is correct
39 Execution timed out 1075 ms 5724 KB Time limit exceeded
40 Execution timed out 1060 ms 5724 KB Time limit exceeded
41 Correct 28 ms 5724 KB Output is correct
42 Execution timed out 1068 ms 5724 KB Time limit exceeded
43 Execution timed out 1068 ms 5724 KB Time limit exceeded
44 Correct 34 ms 5724 KB Output is correct
45 Execution timed out 1060 ms 5724 KB Time limit exceeded
46 Execution timed out 1022 ms 5720 KB Time limit exceeded
47 Correct 43 ms 5976 KB Output is correct
48 Execution timed out 1041 ms 5976 KB Time limit exceeded
49 Execution timed out 1073 ms 5980 KB Time limit exceeded
50 Correct 44 ms 5976 KB Output is correct
51 Execution timed out 1068 ms 5980 KB Time limit exceeded
52 Execution timed out 1050 ms 5980 KB Time limit exceeded
53 Correct 81 ms 5980 KB Output is correct
54 Execution timed out 1070 ms 5980 KB Time limit exceeded
55 Execution timed out 1082 ms 5980 KB Time limit exceeded
56 Correct 68 ms 5980 KB Output is correct
57 Execution timed out 1054 ms 5980 KB Time limit exceeded
58 Execution timed out 1047 ms 5980 KB Time limit exceeded
59 Correct 73 ms 5980 KB Output is correct
60 Execution timed out 1020 ms 5976 KB Time limit exceeded
61 Execution timed out 1048 ms 5976 KB Time limit exceeded
62 Correct 89 ms 6228 KB Output is correct
63 Correct 43 ms 5980 KB Output is correct
64 Execution timed out 1064 ms 5972 KB Time limit exceeded
65 Execution timed out 1049 ms 5980 KB Time limit exceeded
66 Execution timed out 1020 ms 5988 KB Time limit exceeded
67 Correct 31 ms 5968 KB Output is correct
68 Correct 33 ms 6236 KB Output is correct
69 Correct 124 ms 6072 KB Output is correct
70 Correct 61 ms 6228 KB Output is correct
71 Correct 44 ms 6060 KB Output is correct
72 Execution timed out 1060 ms 6236 KB Time limit exceeded
73 Incorrect 571 ms 7732 KB Output isn't correct
74 Execution timed out 1038 ms 7508 KB Time limit exceeded
75 Correct 597 ms 7760 KB Output is correct
76 Correct 357 ms 7732 KB Output is correct
77 Correct 864 ms 7736 KB Output is correct
78 Correct 40 ms 7508 KB Output is correct
79 Correct 978 ms 7764 KB Output is correct
80 Correct 501 ms 7508 KB Output is correct
81 Correct 307 ms 7688 KB Output is correct
82 Correct 768 ms 7616 KB Output is correct
83 Correct 45 ms 7228 KB Output is correct
84 Correct 689 ms 7448 KB Output is correct
85 Correct 349 ms 7248 KB Output is correct
86 Correct 195 ms 7196 KB Output is correct
87 Correct 490 ms 7328 KB Output is correct
88 Correct 48 ms 7072 KB Output is correct
89 Correct 465 ms 6992 KB Output is correct
90 Correct 216 ms 7004 KB Output is correct
91 Correct 329 ms 7152 KB Output is correct
92 Correct 127 ms 6996 KB Output is correct