oj.uz

Submission #334269

# Submission time Handle Problem Language Result Execution time Memory
334269 2020-12-08T22:25:36 Z Fischer Brunhilda’s Birthday (BOI13_brunhilda) C++14
63.6508 / 100
 1000 ms 262148 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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