Submission #385865

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
385865	2021-04-05T07:02:38 Z	wind_reaper	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	344 ms	80876 KB

brunhilda

#include <bits/stdc++.h>

using namespace std;

const int MXN = 10000001;
const int INF = 1000000000;

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int M, Q;
	cin >> M >> Q;

	vector<int> P(M), LP(MXN);
	for(auto& p : P){
		cin >> p;
		for(int i = 0; i < MXN; i += p)
			LP[i] = p;
	}

	vector<int> dp(MXN);
	int cur = 0;
	for(int i = 1; i < MXN; i++){
		while(cur + LP[cur] <= i) cur++;
		if(cur >= i) dp[i] = MXN + 10;
		else dp[i] = dp[cur] + 1;
	}

	while(Q--){
		int x;
		cin >> x;
		if(dp[x] >= MXN) cout << "oo\n";
		else cout << dp[x] << '\n';
	}
	return 0;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	78584 KB	Output is correct
2	Correct	141 ms	78656 KB	Output is correct
3	Correct	138 ms	78572 KB	Output is correct
4	Correct	106 ms	78700 KB	Output is correct
5	Correct	133 ms	78636 KB	Output is correct
6	Correct	124 ms	78572 KB	Output is correct
7	Correct	135 ms	78572 KB	Output is correct
8	Correct	148 ms	78572 KB	Output is correct
9	Correct	160 ms	78572 KB	Output is correct
10	Correct	195 ms	78612 KB	Output is correct
11	Correct	160 ms	78572 KB	Output is correct
12	Correct	107 ms	78620 KB	Output is correct
13	Correct	262 ms	78572 KB	Output is correct
14	Correct	255 ms	78720 KB	Output is correct
15	Correct	154 ms	78700 KB	Output is correct
16	Correct	144 ms	78572 KB	Output is correct
17	Correct	136 ms	78688 KB	Output is correct
18	Correct	106 ms	78732 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	117 ms	78700 KB	Output is correct
2	Correct	153 ms	79724 KB	Output is correct
3	Correct	313 ms	79452 KB	Output is correct
4	Correct	139 ms	78828 KB	Output is correct
5	Correct	227 ms	79232 KB	Output is correct
6	Correct	133 ms	78584 KB	Output is correct
7	Correct	118 ms	78700 KB	Output is correct
8	Correct	140 ms	78572 KB	Output is correct
9	Correct	252 ms	79476 KB	Output is correct
10	Correct	314 ms	79304 KB	Output is correct
11	Correct	301 ms	79064 KB	Output is correct
12	Correct	182 ms	78592 KB	Output is correct
13	Correct	114 ms	78708 KB	Output is correct
14	Correct	149 ms	78700 KB	Output is correct
15	Correct	266 ms	79028 KB	Output is correct
16	Correct	132 ms	79724 KB	Output is correct
17	Correct	275 ms	78612 KB	Output is correct
18	Correct	261 ms	79724 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	274 ms	79648 KB	Output is correct
2	Correct	322 ms	79436 KB	Output is correct
3	Correct	326 ms	79852 KB	Output is correct
4	Correct	218 ms	79596 KB	Output is correct
5	Correct	163 ms	80748 KB	Output is correct
6	Correct	302 ms	79652 KB	Output is correct
7	Correct	228 ms	80388 KB	Output is correct
8	Correct	267 ms	79596 KB	Output is correct
9	Correct	268 ms	79724 KB	Output is correct
10	Correct	199 ms	78828 KB	Output is correct
11	Correct	177 ms	78956 KB	Output is correct
12	Correct	237 ms	79084 KB	Output is correct
13	Correct	298 ms	79980 KB	Output is correct
14	Correct	208 ms	79980 KB	Output is correct
15	Correct	255 ms	79116 KB	Output is correct
16	Correct	283 ms	78956 KB	Output is correct
17	Correct	240 ms	79212 KB	Output is correct
18	Correct	325 ms	79468 KB	Output is correct
19	Correct	125 ms	78956 KB	Output is correct
20	Correct	317 ms	79724 KB	Output is correct
21	Correct	228 ms	79980 KB	Output is correct
22	Correct	337 ms	80748 KB	Output is correct
23	Correct	166 ms	79980 KB	Output is correct
24	Correct	140 ms	79596 KB	Output is correct
25	Correct	227 ms	79852 KB	Output is correct
26	Correct	211 ms	79724 KB	Output is correct
27	Correct	344 ms	80260 KB	Output is correct
28	Correct	138 ms	79724 KB	Output is correct
29	Correct	304 ms	80748 KB	Output is correct
30	Correct	275 ms	80492 KB	Output is correct
31	Correct	156 ms	79596 KB	Output is correct
32	Correct	172 ms	79596 KB	Output is correct
33	Correct	130 ms	79596 KB	Output is correct
34	Correct	229 ms	80364 KB	Output is correct
35	Correct	144 ms	79724 KB	Output is correct
36	Correct	331 ms	80620 KB	Output is correct
37	Correct	160 ms	80876 KB	Output is correct
38	Correct	272 ms	79852 KB	Output is correct
39	Correct	150 ms	79724 KB	Output is correct
40	Correct	236 ms	79652 KB	Output is correct
41	Correct	213 ms	80236 KB	Output is correct
42	Correct	289 ms	79852 KB	Output is correct