Submission #256255

# Submission time Handle Problem Language Result Execution time Memory
256255 2020-08-02T12:27:31 Z Saboon Brunhilda’s Birthday (BOI13_brunhilda) C++14
46.9841 / 100
809 ms 262148 KB
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
 
const int maxn = 1e7 + 10;

int cnt[maxn];
int last[maxn], pre[6*maxn], p[6*maxn];
int Q[6*maxn], tail, head;
int dp[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int m, q;
	cin >> m >> q;
	int sz = 0;
	memset(last, -1, sizeof last);
	for (int i = 0; i < m; i++){
		int x;
		cin >> x;
		p[sz] = x, pre[sz] = last[0], last[0] = sz ++;
	}
	int n = 1000*1000*10;
	int mxm = n+1;
	for (int i = 0; i <= n; i++){
		while (last[i] != -1){
			int idx = last[i];
			if (i > 0)
				cnt[i-p[idx]] ++;
			Q[head++] = i;
			if (i+p[idx] <= n)
				p[sz] = p[idx], pre[sz] = last[i+p[idx]], last[i+p[idx]] = sz ++;
			last[i] = pre[last[i]];
		}
		while (tail < head and cnt[Q[tail]] > 0)
			cnt[Q[tail++]] --;
		if (i > 0){
			if (Q[tail] == i){
				dp[i] = -1;
				mxm = i;
				break;
			}
			dp[i] = dp[Q[tail]] + 1;
		}
	}
	while (q --){
		int x;
		cin >> x;
		if (x >= mxm)
			cout << "oo\n";
		else
			cout << dp[x] << '\n';
	}
}
# Verdict Execution time Memory Grader output
1 Correct 24 ms 39552 KB Output is correct
2 Correct 284 ms 238712 KB Output is correct
3 Correct 27 ms 44024 KB Output is correct
4 Correct 144 ms 126844 KB Output is correct
5 Correct 185 ms 152824 KB Output is correct
6 Correct 24 ms 39552 KB Output is correct
7 Correct 27 ms 44032 KB Output is correct
8 Correct 47 ms 58488 KB Output is correct
9 Runtime error 376 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 379 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Correct 347 ms 245624 KB Output is correct
12 Correct 114 ms 124152 KB Output is correct
13 Runtime error 439 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 434 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Correct 330 ms 235128 KB Output is correct
16 Correct 285 ms 238712 KB Output is correct
17 Correct 203 ms 153208 KB Output is correct
18 Correct 171 ms 126840 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 221 ms 138360 KB Output is correct
2 Correct 220 ms 146856 KB Output is correct
3 Runtime error 681 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 241 ms 175480 KB Output is correct
5 Runtime error 586 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Correct 247 ms 202232 KB Output is correct
7 Correct 179 ms 138360 KB Output is correct
8 Correct 220 ms 169208 KB Output is correct
9 Runtime error 624 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 640 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 594 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 420 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Correct 176 ms 149112 KB Output is correct
14 Correct 242 ms 175608 KB Output is correct
15 Runtime error 579 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Correct 222 ms 146808 KB Output is correct
17 Runtime error 441 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 607 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Runtime error 679 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 642 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 664 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 437 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Correct 462 ms 147196 KB Output is correct
6 Runtime error 462 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 747 ms 236024 KB Output is correct
8 Runtime error 584 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 581 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Correct 440 ms 253564 KB Output is correct
11 Correct 384 ms 218104 KB Output is correct
12 Runtime error 465 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 636 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 389 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 473 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 474 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 597 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 636 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Correct 277 ms 172920 KB Output is correct
20 Runtime error 754 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 402 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 645 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Correct 555 ms 151288 KB Output is correct
24 Correct 367 ms 141308 KB Output is correct
25 Runtime error 444 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 419 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 729 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Correct 450 ms 166008 KB Output is correct
29 Runtime error 731 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 809 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Correct 446 ms 171772 KB Output is correct
32 Correct 471 ms 189816 KB Output is correct
33 Correct 314 ms 130936 KB Output is correct
34 Correct 683 ms 236152 KB Output is correct
35 Correct 415 ms 169028 KB Output is correct
36 Runtime error 631 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Correct 455 ms 147192 KB Output is correct
38 Runtime error 464 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Correct 407 ms 148348 KB Output is correct
40 Runtime error 574 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 591 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 490 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)