Submission #256265

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
256265	2020-08-02T12:53:03 Z	Saboon	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	60.3175 / 100	1000 ms	262148 KB

brunhilda

#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[maxn], p[maxn];
int Q[maxn], CQ[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]] ++;
			if (tail == head or Q[head-1] != i)
				Q[head++] = i;
			CQ[head-1] ++;
			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]] == CQ[tail])
			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';
	}
}

Subtask #1

16.6666666667 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	39544 KB	Output is correct
2	Correct	271 ms	252920 KB	Output is correct
3	Correct	26 ms	44544 KB	Output is correct
4	Correct	142 ms	129528 KB	Output is correct
5	Correct	161 ms	161784 KB	Output is correct
6	Correct	23 ms	39680 KB	Output is correct
7	Correct	26 ms	44544 KB	Output is correct
8	Correct	49 ms	59768 KB	Output is correct
9	Correct	362 ms	260344 KB	Output is correct
10	Runtime error	399 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Correct	322 ms	250728 KB	Output is correct
12	Correct	114 ms	126288 KB	Output is correct
13	Runtime error	919 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	982 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Correct	306 ms	251128 KB	Output is correct
16	Correct	289 ms	252952 KB	Output is correct
17	Correct	181 ms	162020 KB	Output is correct
18	Correct	143 ms	129656 KB	Output is correct

Subtask #2

12.2222222222 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	178 ms	144764 KB	Output is correct
2	Correct	227 ms	154744 KB	Output is correct
3	Execution timed out	1080 ms	262144 KB	Time limit exceeded
4	Correct	227 ms	188024 KB	Output is correct
5	Correct	591 ms	259192 KB	Output is correct
6	Correct	235 ms	220924 KB	Output is correct
7	Correct	184 ms	144828 KB	Output is correct
8	Correct	212 ms	180344 KB	Output is correct
9	Runtime error	760 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Execution timed out	1062 ms	262144 KB	Time limit exceeded
11	Execution timed out	1103 ms	262144 KB	Time limit exceeded
12	Correct	377 ms	255740 KB	Output is correct
13	Correct	165 ms	157816 KB	Output is correct
14	Correct	256 ms	188024 KB	Output is correct
15	Execution timed out	1049 ms	262144 KB	Time limit exceeded
16	Correct	241 ms	154744 KB	Output is correct
17	Runtime error	930 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	801 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3

31.4285714286 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1102 ms	262144 KB	Time limit exceeded
2	Execution timed out	1104 ms	262144 KB	Time limit exceeded
3	Execution timed out	1074 ms	262144 KB	Time limit exceeded
4	Correct	611 ms	259372 KB	Output is correct
5	Correct	489 ms	156024 KB	Output is correct
6	Runtime error	535 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Correct	786 ms	251692 KB	Output is correct
8	Execution timed out	1094 ms	262144 KB	Time limit exceeded
9	Execution timed out	1087 ms	262144 KB	Time limit exceeded
10	Correct	451 ms	250616 KB	Output is correct
11	Correct	411 ms	231032 KB	Output is correct
12	Runtime error	505 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Execution timed out	1093 ms	262144 KB	Time limit exceeded
14	Runtime error	410 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Runtime error	941 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	891 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Correct	700 ms	260860 KB	Output is correct
18	Execution timed out	1052 ms	262144 KB	Time limit exceeded
19	Correct	253 ms	187256 KB	Output is correct
20	Execution timed out	1107 ms	262144 KB	Time limit exceeded
21	Runtime error	462 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Execution timed out	1107 ms	262144 KB	Time limit exceeded
23	Correct	463 ms	162168 KB	Output is correct
24	Correct	362 ms	147960 KB	Output is correct
25	Correct	610 ms	256632 KB	Output is correct
26	Correct	599 ms	259320 KB	Output is correct
27	Execution timed out	1106 ms	262144 KB	Time limit exceeded
28	Correct	394 ms	177656 KB	Output is correct
29	Runtime error	741 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
30	Correct	841 ms	261624 KB	Output is correct
31	Correct	424 ms	183672 KB	Output is correct
32	Correct	458 ms	203152 KB	Output is correct
33	Correct	352 ms	135032 KB	Output is correct
34	Correct	698 ms	251808 KB	Output is correct
35	Correct	436 ms	180984 KB	Output is correct
36	Execution timed out	1103 ms	262144 KB	Time limit exceeded
37	Correct	470 ms	156280 KB	Output is correct
38	Runtime error	568 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Correct	390 ms	156664 KB	Output is correct
40	Correct	685 ms	262144 KB	Output is correct
41	Correct	651 ms	259320 KB	Output is correct
42	Runtime error	874 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)