oj.uz

Submission #256303

# Submission time Handle Problem Language Result Execution time Memory
256303 2020-08-02T13:58:19 Z Saboon Brunhilda’s Birthday (BOI13_brunhilda) C++14
86.0317 / 100
 1000 ms 213624 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;
 
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;
		cnt[0] ++;
		p[sz] = x, pre[sz] = last[x], last[x] = sz ++;
	}
	Q[head++] = 0;
	int n = 1000*1000*10;
	int mxm = n+1;
	for (int i = 1; i <= n; i++){
		while (last[i] != -1){
			int idx = last[i];
			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 (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 256 ms 204968 KB Output is correct
3 Correct 27 ms 43264 KB Output is correct
4 Correct 135 ms 107128 KB Output is correct
5 Correct 153 ms 131832 KB Output is correct
6 Correct 24 ms 39552 KB Output is correct
7 Correct 27 ms 43256 KB Output is correct
8 Correct 45 ms 55416 KB Output is correct
9 Correct 337 ms 208504 KB Output is correct
10 Correct 386 ms 209600 KB Output is correct
11 Correct 305 ms 203896 KB Output is correct
12 Correct 119 ms 104696 KB Output is correct
13 Correct 555 ms 212920 KB Output is correct
14 Correct 568 ms 213076 KB Output is correct
15 Correct 293 ms 204044 KB Output is correct
16 Correct 276 ms 204936 KB Output is correct
17 Correct 177 ms 132088 KB Output is correct
18 Correct 135 ms 107128 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 118648 KB Output is correct
2 Correct 247 ms 126840 KB Output is correct
3 Execution timed out 1006 ms 213340 KB Time limit exceeded
4 Correct 222 ms 152568 KB Output is correct
5 Correct 626 ms 207864 KB Output is correct
6 Correct 251 ms 177912 KB Output is correct
7 Correct 191 ms 118520 KB Output is correct
8 Correct 235 ms 146528 KB Output is correct
9 Correct 690 ms 210040 KB Output is correct
10 Correct 973 ms 213496 KB Output is correct
11 Correct 931 ms 213216 KB Output is correct
12 Correct 353 ms 206456 KB Output is correct
13 Correct 154 ms 128712 KB Output is correct
14 Correct 247 ms 152568 KB Output is correct
15 Correct 797 ms 212108 KB Output is correct
16 Correct 213 ms 126740 KB Output is correct
17 Correct 571 ms 212588 KB Output is correct
18 Correct 725 ms 210704 KB Output is correct

Subtask #3
47.1428571429 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 212728 KB Output is correct
2 Execution timed out 1048 ms 213284 KB Time limit exceeded
3 Execution timed out 1098 ms 213488 KB Time limit exceeded
4 Correct 564 ms 207864 KB Output is correct
5 Correct 440 ms 126968 KB Output is correct
6 Correct 736 ms 211516 KB Output is correct
7 Correct 751 ms 204476 KB Output is correct
8 Execution timed out 1012 ms 212856 KB Time limit exceeded
9 Correct 929 ms 212856 KB Output is correct
10 Correct 398 ms 203768 KB Output is correct
11 Correct 358 ms 188280 KB Output is correct
12 Correct 546 ms 210992 KB Output is correct
13 Correct 931 ms 212336 KB Output is correct
14 Correct 592 ms 210868 KB Output is correct
15 Correct 614 ms 212600 KB Output is correct
16 Correct 690 ms 212964 KB Output is correct
17 Correct 793 ms 208632 KB Output is correct
18 Execution timed out 1105 ms 208248 KB Time limit exceeded
19 Correct 234 ms 151344 KB Output is correct
20 Execution timed out 1096 ms 199544 KB Time limit exceeded
21 Correct 643 ms 212216 KB Output is correct
22 Execution timed out 1106 ms 208272 KB Time limit exceeded
23 Correct 486 ms 131368 KB Output is correct
24 Correct 391 ms 121080 KB Output is correct
25 Correct 624 ms 206584 KB Output is correct
26 Correct 580 ms 207992 KB Output is correct
27 Execution timed out 1109 ms 213624 KB Time limit exceeded
28 Correct 391 ms 144248 KB Output is correct
29 Execution timed out 1089 ms 210440 KB Time limit exceeded
30 Correct 806 ms 208824 KB Output is correct
31 Correct 399 ms 149268 KB Output is correct
32 Correct 439 ms 164856 KB Output is correct
33 Correct 317 ms 111224 KB Output is correct
34 Correct 598 ms 204280 KB Output is correct
35 Correct 400 ms 146960 KB Output is correct
36 Execution timed out 1113 ms 213624 KB Time limit exceeded
37 Correct 448 ms 126964 KB Output is correct
38 Correct 723 ms 211324 KB Output is correct
39 Correct 401 ms 127860 KB Output is correct
40 Correct 657 ms 209784 KB Output is correct
41 Correct 642 ms 208120 KB Output is correct
42 Correct 818 ms 213352 KB Output is correct