Submission #256298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
256298	2020-08-02T13:53:49 Z	Saboon	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	90.3175 / 100	1000 ms	215032 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;
 
short cnt[maxn];
int last[maxn], pre[maxn], p[maxn];
int Q[maxn], tail, head;
int dp[maxn];
bitset<maxn> mark;
 
int main(){
	ios_base::sync_with_stdio(false);
	int m, q;
	cin >> m >> q;
	int sz = 0;
	memset(last, -1, sizeof last);
	int mxmp = 0;
	for (int i = 0; i < m; i++){
		int x;
		cin >> x;
		if (mark[x])
			continue;
		mxmp = max(mxmp, x);
		mark[x] = 1;
		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 ++;
				if (sz == maxn)
					sz = 0;
			}
			last[i] = pre[last[i]];
		}
		if (tail == 0){
			if (i >= mxmp)
				tail ++;
			else
				cnt[0] = 1;
		}
		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

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	39552 KB	Output is correct
2	Correct	257 ms	204920 KB	Output is correct
3	Correct	26 ms	43256 KB	Output is correct
4	Correct	132 ms	107128 KB	Output is correct
5	Correct	173 ms	131832 KB	Output is correct
6	Correct	23 ms	39552 KB	Output is correct
7	Correct	26 ms	43256 KB	Output is correct
8	Correct	45 ms	55416 KB	Output is correct
9	Correct	350 ms	208564 KB	Output is correct
10	Correct	396 ms	209660 KB	Output is correct
11	Correct	307 ms	203896 KB	Output is correct
12	Correct	109 ms	104528 KB	Output is correct
13	Correct	545 ms	212948 KB	Output is correct
14	Correct	550 ms	212984 KB	Output is correct
15	Correct	274 ms	204024 KB	Output is correct
16	Correct	251 ms	204920 KB	Output is correct
17	Correct	169 ms	132216 KB	Output is correct
18	Correct	136 ms	107128 KB	Output is correct

Subtask #2

18.8888888889 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	185 ms	118708 KB	Output is correct
2	Correct	210 ms	128248 KB	Output is correct
3	Correct	985 ms	213880 KB	Output is correct
4	Correct	218 ms	152568 KB	Output is correct
5	Correct	569 ms	208248 KB	Output is correct
6	Correct	240 ms	177992 KB	Output is correct
7	Correct	173 ms	118776 KB	Output is correct
8	Correct	209 ms	146552 KB	Output is correct
9	Correct	718 ms	210484 KB	Output is correct
10	Execution timed out	1036 ms	213812 KB	Time limit exceeded
11	Correct	992 ms	213452 KB	Output is correct
12	Correct	362 ms	206456 KB	Output is correct
13	Correct	157 ms	128760 KB	Output is correct
14	Correct	224 ms	152696 KB	Output is correct
15	Correct	746 ms	212452 KB	Output is correct
16	Correct	217 ms	128152 KB	Output is correct
17	Correct	554 ms	212600 KB	Output is correct
18	Correct	739 ms	211492 KB	Output is correct

Subtask #3

51.4285714286 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	870 ms	213584 KB	Output is correct
2	Execution timed out	1002 ms	214040 KB	Time limit exceeded
3	Execution timed out	1101 ms	214264 KB	Time limit exceeded
4	Correct	611 ms	208504 KB	Output is correct
5	Correct	449 ms	129272 KB	Output is correct
6	Correct	726 ms	212228 KB	Output is correct
7	Correct	627 ms	205944 KB	Output is correct
8	Correct	871 ms	213520 KB	Output is correct
9	Correct	867 ms	213624 KB	Output is correct
10	Correct	391 ms	203896 KB	Output is correct
11	Correct	358 ms	188544 KB	Output is correct
12	Correct	541 ms	211320 KB	Output is correct
13	Correct	971 ms	213344 KB	Output is correct
14	Correct	585 ms	211576 KB	Output is correct
15	Correct	614 ms	212984 KB	Output is correct
16	Correct	672 ms	213240 KB	Output is correct
17	Correct	699 ms	209144 KB	Output is correct
18	Correct	998 ms	213880 KB	Output is correct
19	Correct	246 ms	151660 KB	Output is correct
20	Execution timed out	1064 ms	214264 KB	Time limit exceeded
21	Correct	643 ms	212984 KB	Output is correct
22	Execution timed out	1108 ms	215032 KB	Time limit exceeded
23	Correct	447 ms	132552 KB	Output is correct
24	Correct	353 ms	121848 KB	Output is correct
25	Correct	606 ms	207276 KB	Output is correct
26	Correct	612 ms	208504 KB	Output is correct
27	Execution timed out	1110 ms	208632 KB	Time limit exceeded
28	Correct	383 ms	145016 KB	Output is correct
29	Correct	935 ms	211960 KB	Output is correct
30	Correct	817 ms	210168 KB	Output is correct
31	Correct	399 ms	149880 KB	Output is correct
32	Correct	439 ms	165624 KB	Output is correct
33	Correct	319 ms	111992 KB	Output is correct
34	Correct	623 ms	205816 KB	Output is correct
35	Correct	408 ms	147860 KB	Output is correct
36	Execution timed out	1108 ms	214748 KB	Time limit exceeded
37	Correct	444 ms	129272 KB	Output is correct
38	Correct	733 ms	212008 KB	Output is correct
39	Correct	393 ms	128760 KB	Output is correct
40	Correct	708 ms	210424 KB	Output is correct
41	Correct	652 ms	209272 KB	Output is correct
42	Correct	808 ms	214264 KB	Output is correct