oj.uz

Submission #334276

# Submission time Handle Problem Language Result Execution time Memory
334276 2020-12-08T22:51:56 Z Fischer Brunhilda’s Birthday (BOI13_brunhilda) C++14
61.1111 / 100
 1000 ms 248684 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[maxn * 5 / 3];
int nxt[maxn * 5 / 3];
int T = 0;
int cnt[maxn];
int dp[maxn];
int p[100010];
 
int main() {
	int m, q;
	scanf("%d%d", &m, &q);
	memset(head, -1, sizeof head);
	for (int i = 0; i < m; ++i) {
		scanf("%d", p+i);
		for (int j=p[i]; j<maxn; j+=p[i]) {
			assert(T < 20 * maxn);
			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 (front < i && cnt[front] == 0) front++;
		if (front == i) dp[i] = mx;
		else dp[i] = min(mx, dp[front] + 1);
	}
	while (q--) {
		int n;
		scanf("%d", &n);
		if (dp[n] > n) puts("oo");
		else printf("%d\n", dp[n]);
	}
	return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%d%d", &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |   scanf("%d", p+i);
      |   ~~~~~^~~~~~~~~~~
brunhilda.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 131820 KB Output is correct
2 Correct 253 ms 198380 KB Output is correct
3 Correct 200 ms 178412 KB Output is correct
4 Correct 125 ms 123756 KB Output is correct
5 Correct 181 ms 141036 KB Output is correct
6 Correct 149 ms 131820 KB Output is correct
7 Correct 208 ms 178284 KB Output is correct
8 Correct 249 ms 205036 KB Output is correct
9 Correct 318 ms 228204 KB Output is correct
10 Correct 363 ms 240364 KB Output is correct
11 Correct 321 ms 203116 KB Output is correct
12 Correct 116 ms 122092 KB Output is correct
13 Execution timed out 1057 ms 213740 KB Time limit exceeded
14 Execution timed out 1112 ms 223724 KB Time limit exceeded
15 Correct 275 ms 195948 KB Output is correct
16 Correct 250 ms 198380 KB Output is correct
17 Correct 205 ms 141420 KB Output is correct
18 Correct 124 ms 123896 KB Output is correct

Subtask #2
13.3333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 131436 KB Output is correct
2 Correct 261 ms 136812 KB Output is correct
3 Execution timed out 363 ms 169964 KB Time limit exceeded (wall clock)
4 Correct 323 ms 156396 KB Output is correct
5 Correct 740 ms 228972 KB Output is correct
6 Correct 230 ms 174060 KB Output is correct
7 Correct 223 ms 131436 KB Output is correct
8 Correct 279 ms 152172 KB Output is correct
9 Correct 944 ms 245840 KB Output is correct
10 Execution timed out 349 ms 169964 KB Time limit exceeded (wall clock)
11 Execution timed out 1072 ms 221676 KB Time limit exceeded
12 Correct 455 ms 214508 KB Output is correct
13 Correct 194 ms 138604 KB Output is correct
14 Correct 309 ms 156268 KB Output is correct
15 Execution timed out 1075 ms 225004 KB Time limit exceeded
16 Correct 258 ms 136812 KB Output is correct
17 Execution timed out 1110 ms 225900 KB Time limit exceeded
18 Incorrect 995 ms 248684 KB Output isn't correct

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1105 ms 225772 KB Time limit exceeded
2 Execution timed out 372 ms 170092 KB Time limit exceeded (wall clock)
3 Execution timed out 352 ms 169932 KB Time limit exceeded (wall clock)
4 Correct 510 ms 225004 KB Output is correct
5 Correct 371 ms 137068 KB Output is correct
6 Execution timed out 1112 ms 233552 KB Time limit exceeded
7 Correct 725 ms 196272 KB Output is correct
8 Execution timed out 1110 ms 225648 KB Time limit exceeded
9 Execution timed out 1112 ms 225216 KB Time limit exceeded
10 Correct 615 ms 208540 KB Output is correct
11 Correct 466 ms 184684 KB Output is correct
12 Execution timed out 1114 ms 242704 KB Time limit exceeded
13 Execution timed out 1080 ms 221548 KB Time limit exceeded
14 Incorrect 434 ms 248428 KB Output isn't correct
15 Execution timed out 1099 ms 226120 KB Time limit exceeded
16 Execution timed out 1114 ms 224364 KB Time limit exceeded
17 Correct 902 ms 236780 KB Output is correct
18 Execution timed out 353 ms 170092 KB Time limit exceeded (wall clock)
19 Correct 208 ms 154348 KB Output is correct
20 Execution timed out 350 ms 170220 KB Time limit exceeded (wall clock)
21 Execution timed out 1115 ms 227436 KB Time limit exceeded
22 Execution timed out 1101 ms 222060 KB Time limit exceeded
23 Correct 403 ms 140012 KB Output is correct
24 Correct 209 ms 133484 KB Output is correct
25 Correct 603 ms 223468 KB Output is correct
26 Correct 512 ms 224876 KB Output is correct
27 Execution timed out 337 ms 169964 KB Time limit exceeded (wall clock)
28 Correct 219 ms 149956 KB Output is correct
29 Execution timed out 1100 ms 236268 KB Time limit exceeded
30 Execution timed out 1052 ms 215180 KB Time limit exceeded
31 Correct 305 ms 153836 KB Output is correct
32 Correct 368 ms 165868 KB Output is correct
33 Correct 168 ms 126604 KB Output is correct
34 Correct 732 ms 196716 KB Output is correct
35 Correct 259 ms 151916 KB Output is correct
36 Execution timed out 1104 ms 223144 KB Time limit exceeded
37 Correct 368 ms 137068 KB Output is correct
38 Execution timed out 1111 ms 234348 KB Time limit exceeded
39 Correct 257 ms 138220 KB Output is correct
40 Correct 702 ms 243948 KB Output is correct
41 Correct 631 ms 217228 KB Output is correct
42 Execution timed out 1114 ms 225644 KB Time limit exceeded