Submission #256267

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
256267	2020-08-02T13:06:02 Z	Saboon	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	70.7936 / 100	1000 ms	262144 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], 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;
			cnt[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)
			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

17.7777777778 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	39552 KB	Output is correct
2	Correct	278 ms	224504 KB	Output is correct
3	Correct	29 ms	43904 KB	Output is correct
4	Correct	148 ms	126712 KB	Output is correct
5	Correct	161 ms	151416 KB	Output is correct
6	Correct	24 ms	39552 KB	Output is correct
7	Correct	30 ms	43896 KB	Output is correct
8	Correct	49 ms	57080 KB	Output is correct
9	Correct	353 ms	228096 KB	Output is correct
10	Correct	367 ms	229112 KB	Output is correct
11	Correct	304 ms	223624 KB	Output is correct
12	Correct	119 ms	124152 KB	Output is correct
13	Runtime error	900 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	904 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Correct	271 ms	223608 KB	Output is correct
16	Correct	260 ms	224508 KB	Output is correct
17	Correct	191 ms	151824 KB	Output is correct
18	Correct	156 ms	126712 KB	Output is correct

Subtask #2

14.4444444444 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	201 ms	138104 KB	Output is correct
2	Correct	272 ms	145912 KB	Output is correct
3	Execution timed out	1083 ms	262144 KB	Time limit exceeded
4	Correct	238 ms	172152 KB	Output is correct
5	Correct	635 ms	227448 KB	Output is correct
6	Correct	238 ms	197496 KB	Output is correct
7	Correct	185 ms	138104 KB	Output is correct
8	Correct	211 ms	166104 KB	Output is correct
9	Correct	709 ms	229880 KB	Output is correct
10	Execution timed out	1115 ms	262144 KB	Time limit exceeded
11	Runtime error	991 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Correct	368 ms	225912 KB	Output is correct
13	Correct	167 ms	148216 KB	Output is correct
14	Correct	226 ms	172152 KB	Output is correct
15	Execution timed out	1067 ms	262144 KB	Time limit exceeded
16	Correct	217 ms	145912 KB	Output is correct
17	Runtime error	860 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Correct	737 ms	230772 KB	Output is correct

Subtask #3

38.5714285714 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1114 ms	262144 KB	Time limit exceeded
2	Execution timed out	1082 ms	262144 KB	Time limit exceeded
3	Runtime error	1043 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Correct	628 ms	227320 KB	Output is correct
5	Correct	479 ms	146808 KB	Output is correct
6	Correct	734 ms	231724 KB	Output is correct
7	Correct	713 ms	223992 KB	Output is correct
8	Execution timed out	1116 ms	262144 KB	Time limit exceeded
9	Execution timed out	1078 ms	262144 KB	Time limit exceeded
10	Correct	397 ms	223224 KB	Output is correct
11	Correct	357 ms	207864 KB	Output is correct
12	Correct	542 ms	230776 KB	Output is correct
13	Execution timed out	1099 ms	262144 KB	Time limit exceeded
14	Correct	585 ms	231164 KB	Output is correct
15	Runtime error	861 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	848 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Correct	667 ms	228216 KB	Output is correct
18	Runtime error	995 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Correct	276 ms	171000 KB	Output is correct
20	Execution timed out	1105 ms	262144 KB	Time limit exceeded
21	Correct	659 ms	232696 KB	Output is correct
22	Execution timed out	1119 ms	262144 KB	Time limit exceeded
23	Correct	495 ms	151124 KB	Output is correct
24	Correct	456 ms	140664 KB	Output is correct
25	Correct	655 ms	226040 KB	Output is correct
26	Correct	615 ms	227444 KB	Output is correct
27	Execution timed out	1102 ms	262144 KB	Time limit exceeded
28	Correct	400 ms	164088 KB	Output is correct
29	Execution timed out	1113 ms	231436 KB	Time limit exceeded
30	Correct	981 ms	228592 KB	Output is correct
31	Correct	429 ms	169008 KB	Output is correct
32	Correct	450 ms	184696 KB	Output is correct
33	Correct	323 ms	131064 KB	Output is correct
34	Correct	652 ms	224248 KB	Output is correct
35	Correct	437 ms	166880 KB	Output is correct
36	Runtime error	1025 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Correct	477 ms	146936 KB	Output is correct
38	Correct	720 ms	231672 KB	Output is correct
39	Correct	387 ms	147704 KB	Output is correct
40	Correct	694 ms	229988 KB	Output is correct
41	Correct	672 ms	227656 KB	Output is correct
42	Runtime error	841 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)