답안 #334269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334269	2020-12-08T22:25:36 Z	Fischer	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	63.6508 / 100	1000 ms	262148 KB

brunhilda

#include <bits/stdc++.h>
#define rep(x, y, z) for (int x = y; x < z; ++x)
#define reo(x, y) for (int x = 0; x < y; ++x)
using namespace std;
 
const int maxn = 1e7 + 10;
int head[maxn];
int val[2 * maxn];
int nxt[2 * maxn];
int T = 0;
int cnt[maxn];
int dp[maxn];
int p[100010];
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int m, q;
	cin >> m >> q;
	memset(head, -1, sizeof head);
	for (int i = 0; i < m; ++i) {
		cin >> p[i];
		for (int j=p[i]; j<maxn; j+=p[i]) {
			nxt[T] = head[j];
			head[j] = T;
			val[T] = j - p[i];
			T++;
		}
	}
	int front = 0;
	cnt[0] = m;
	const int mx = 1e9;
	for (int i = 1; i < maxn; ++i) {
		for (int x = head[i]; ~x; x = nxt[x]) {
			cnt[i]++;
			cnt[val[x]]--;
		}
		while (cnt[front] == 0) front++;
		if (front == i) dp[i] = mx;
		else dp[i] = min(mx, dp[front] + 1);
	}
	while (q--) {
		int n;
		cin >> n;
		if (dp[n] > n) cout << "oo\n";
		else cout << dp[n] << '\n';
	}
	return 0;
}

Subtask #1

17.7777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	149 ms	131820 KB	Output is correct
2	Correct	248 ms	198380 KB	Output is correct
3	Correct	206 ms	178284 KB	Output is correct
4	Correct	129 ms	123756 KB	Output is correct
5	Correct	184 ms	141036 KB	Output is correct
6	Correct	154 ms	131968 KB	Output is correct
7	Correct	197 ms	178284 KB	Output is correct
8	Correct	246 ms	204908 KB	Output is correct
9	Correct	317 ms	228332 KB	Output is correct
10	Correct	365 ms	240620 KB	Output is correct
11	Correct	313 ms	203116 KB	Output is correct
12	Correct	122 ms	122092 KB	Output is correct
13	Execution timed out	1103 ms	258924 KB	Time limit exceeded
14	Execution timed out	1110 ms	260048 KB	Time limit exceeded
15	Correct	272 ms	196076 KB	Output is correct
16	Correct	253 ms	198380 KB	Output is correct
17	Correct	214 ms	141548 KB	Output is correct
18	Correct	127 ms	123756 KB	Output is correct

Subtask #2

14.4444444444 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	253 ms	131440 KB	Output is correct
2	Correct	277 ms	136836 KB	Output is correct
3	Execution timed out	1112 ms	248172 KB	Time limit exceeded
4	Correct	325 ms	156332 KB	Output is correct
5	Correct	820 ms	229080 KB	Output is correct
6	Correct	232 ms	174060 KB	Output is correct
7	Correct	227 ms	131564 KB	Output is correct
8	Correct	285 ms	152044 KB	Output is correct
9	Correct	956 ms	246036 KB	Output is correct
10	Execution timed out	1118 ms	248172 KB	Time limit exceeded
11	Execution timed out	1115 ms	248044 KB	Time limit exceeded
12	Correct	460 ms	214636 KB	Output is correct
13	Correct	175 ms	138604 KB	Output is correct
14	Correct	317 ms	156312 KB	Output is correct
15	Runtime error	892 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Correct	256 ms	136940 KB	Output is correct
17	Execution timed out	1119 ms	255340 KB	Time limit exceeded
18	Correct	937 ms	257516 KB	Output is correct

Subtask #3

31.4285714286 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1099 ms	262144 KB	Time limit exceeded
2	Execution timed out	1093 ms	247216 KB	Time limit exceeded
3	Execution timed out	1120 ms	247788 KB	Time limit exceeded
4	Correct	515 ms	224976 KB	Output is correct
5	Correct	367 ms	137068 KB	Output is correct
6	Runtime error	751 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Correct	727 ms	196332 KB	Output is correct
8	Execution timed out	1063 ms	262148 KB	Time limit exceeded
9	Execution timed out	1080 ms	262148 KB	Time limit exceeded
10	Correct	615 ms	208448 KB	Output is correct
11	Correct	472 ms	184812 KB	Output is correct
12	Runtime error	705 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Execution timed out	1113 ms	236652 KB	Time limit exceeded
14	Correct	418 ms	250476 KB	Output is correct
15	Execution timed out	1108 ms	262148 KB	Time limit exceeded
16	Execution timed out	1117 ms	250152 KB	Time limit exceeded
17	Correct	909 ms	236568 KB	Output is correct
18	Execution timed out	1121 ms	248172 KB	Time limit exceeded
19	Correct	212 ms	154476 KB	Output is correct
20	Execution timed out	1119 ms	247916 KB	Time limit exceeded
21	Runtime error	458 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Execution timed out	1121 ms	249452 KB	Time limit exceeded
23	Correct	405 ms	140012 KB	Output is correct
24	Correct	208 ms	133484 KB	Output is correct
25	Correct	596 ms	224108 KB	Output is correct
26	Correct	515 ms	225516 KB	Output is correct
27	Execution timed out	1084 ms	237488 KB	Time limit exceeded
28	Correct	224 ms	149984 KB	Output is correct
29	Execution timed out	1116 ms	236396 KB	Time limit exceeded
30	Execution timed out	1028 ms	215916 KB	Time limit exceeded
31	Correct	304 ms	153964 KB	Output is correct
32	Correct	358 ms	165868 KB	Output is correct
33	Correct	172 ms	126712 KB	Output is correct
34	Correct	741 ms	196312 KB	Output is correct
35	Correct	259 ms	152044 KB	Output is correct
36	Execution timed out	1113 ms	250092 KB	Time limit exceeded
37	Correct	363 ms	137068 KB	Output is correct
38	Runtime error	748 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Correct	252 ms	138348 KB	Output is correct
40	Correct	716 ms	244588 KB	Output is correct
41	Correct	630 ms	217324 KB	Output is correct
42	Execution timed out	1118 ms	251500 KB	Time limit exceeded