Submission #104092

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104092	2019-04-04T02:30:30 Z	Erkhemkhuu	Mecho (IOI09_mecho)	C++17	12 / 100	170 ms	7688 KB

mecho

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
int movex[4] = {-1, 0, 1, 0};
int movey[4] = {0, 1, 0, -1};
string maps[805];
int beeStep[805][805], meStep[805][805], n, Mx, My, s, Dx, Dy;
queue <pair <int, int> > bee, me;

inline bool can(int mid) {
	if(mid >= beeStep[Mx][My]) return false;
	int curx, cury, curstep, i, j, i1, movexx, moveyy;
	me.push({Mx, My});
	for(i = 0; i <= n; i++) 
		for(j = 0; j <= n; j++) 
			meStep[i][j] = INT_MAX;
	meStep[Mx][My] = 0;
	while(!me.empty()) {
		curx = me.front().F;
		cury = me.front().S;
		me.pop();
		for(i = 0; i < 4; i++) {
			movexx = movex[i] + curx;
			moveyy = movey[i] + cury;
			if(maps[movexx][moveyy] == 'D') {
				while(!me.empty())
					me.pop();
				return true;	
			}
			if((maps[movexx][moveyy] == 'G' || maps[movexx][moveyy] == 'D') && meStep[curx][cury] + 1 < s * (beeStep[movexx][moveyy] - mid) && meStep[movexx][moveyy] == INT_MAX) {
				meStep[movexx][moveyy] = meStep[curx][cury] + 1;
				me.push(mp(movexx, moveyy));
			} 
		}
	}
	return false;
}
int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio;
	int i, j, l, r, curx, cury, curstep, movexx, moveyy, mid;
	cin >> n >> s;
	memset(beeStep, -1, sizeof(beeStep));
	for(i = 0; i < n; i++) {
		cin >> maps[i];
		for(j = 0; j < n; j++) {
			if(maps[i][j] == 'H') {
				bee.push(mp(i, j));
				beeStep[i][j] = 0;
			}
			if(maps[i][j] == 'M') {
				Mx = i; My = j;
			}
			if(maps[i][j] == 'D') {
				Dx = i; Dy = j;
			}
		}
	}
	while(!bee.empty()) {
		curx = bee.front().F;
		cury = bee.front().S;
		bee.pop();
		for(i = 0; i < 4; i++) {
			movexx = movex[i] + curx;
			moveyy = movey[i] + cury;
			if((maps[movexx][moveyy] == 'G' || maps[movexx][moveyy] == 'M') && beeStep[movexx][moveyy] == -1) {
				beeStep[movexx][moveyy] = beeStep[curx][cury] + 1;
				bee.push(mp(movexx, moveyy));
			}
		}
	}
	if(!can(0)) {
		cout << "-1\n";
		return 0;
	}
	l = 0; r = 1e9;
	while(l != r) {
		mid = (l + r + 1) / 2;
		if(can(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << "\n";
	return 0;
}

Compilation message

mecho.cpp: In function 'bool can(int)':
mecho.cpp:16:18: warning: unused variable 'curstep' [-Wunused-variable]
  int curx, cury, curstep, i, j, i1, movexx, moveyy;
                  ^~~~~~~
mecho.cpp:16:33: warning: unused variable 'i1' [-Wunused-variable]
  int curx, cury, curstep, i, j, i1, movexx, moveyy;
                                 ^~
mecho.cpp: In function 'int main()':
mecho.cpp:45:27: warning: statement is a reference, not call, to function 'std::ios_base::sync_with_stdio' [-Waddress]
  ios_base::sync_with_stdio;
                           ^
mecho.cpp:45:27: warning: statement has no effect [-Wunused-value]
mecho.cpp:46:30: warning: unused variable 'curstep' [-Wunused-variable]
  int i, j, l, r, curx, cury, curstep, movexx, moveyy, mid;
                              ^~~~~~~

Subtask #1

12.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	10 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	8 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	11 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	8 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	47 ms	7416 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	9 ms	5600 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	10 ms	5656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	11 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	9 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	11 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Correct	7 ms	3124 KB	Output is correct
14	Correct	6 ms	3072 KB	Output is correct
15	Runtime error	9 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	9 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	9 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	10 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	9 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Runtime error	10 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Runtime error	8 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	8 ms	5504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	11 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Runtime error	9 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
26	Runtime error	10 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Runtime error	8 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Runtime error	9 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Runtime error	10 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Runtime error	10 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Runtime error	10 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Runtime error	9 ms	5632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
33	Runtime error	14 ms	5888 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Runtime error	18 ms	6016 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	14 ms	6016 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	19 ms	5888 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Runtime error	16 ms	5888 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Runtime error	17 ms	6016 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	25 ms	6136 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Runtime error	14 ms	6008 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Runtime error	17 ms	6016 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Runtime error	31 ms	6520 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Runtime error	23 ms	6520 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
44	Runtime error	18 ms	6528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	24 ms	6648 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Runtime error	18 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
47	Runtime error	20 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	25 ms	6776 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Runtime error	22 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
50	Runtime error	23 ms	6656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
51	Runtime error	32 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
52	Runtime error	24 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	24 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Runtime error	31 ms	6904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
55	Runtime error	27 ms	6912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
56	Runtime error	25 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
57	Runtime error	35 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
58	Runtime error	29 ms	7004 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
59	Runtime error	25 ms	7040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
60	Runtime error	40 ms	7032 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
61	Runtime error	30 ms	7168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
62	Runtime error	29 ms	7160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
63	Runtime error	29 ms	7168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	31 ms	7132 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	34 ms	7032 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	37 ms	7160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	36 ms	7160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	28 ms	7160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	29 ms	7168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	43 ms	7160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	43 ms	7160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	37 ms	7160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	32 ms	7168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	31 ms	7160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	73 ms	7672 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	73 ms	7676 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	62 ms	7688 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Correct	57 ms	6392 KB	Output is correct
79	Correct	142 ms	6416 KB	Output is correct
80	Correct	102 ms	6492 KB	Output is correct
81	Correct	100 ms	6400 KB	Output is correct
82	Correct	103 ms	6520 KB	Output is correct
83	Runtime error	47 ms	7544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Correct	135 ms	6364 KB	Output is correct
85	Correct	129 ms	6468 KB	Output is correct
86	Correct	144 ms	6592 KB	Output is correct
87	Correct	128 ms	6364 KB	Output is correct
88	Runtime error	56 ms	7516 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Correct	157 ms	6364 KB	Output is correct
90	Correct	170 ms	6392 KB	Output is correct
91	Correct	145 ms	6392 KB	Output is correct
92	Correct	156 ms	6392 KB	Output is correct