oj.uz

답안 #256277

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256277 2020-08-02T13:13:00 Z Saboon Brunhilda’s Birthday (BOI13_brunhilda) C++14
79.2064 / 100
 1000 ms 212344 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;
		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]];
		}
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 39544 KB Output is correct
2 Correct 249 ms 204920 KB Output is correct
3 Correct 31 ms 43264 KB Output is correct
4 Correct 135 ms 107128 KB Output is correct
5 Correct 165 ms 131832 KB Output is correct
6 Correct 29 ms 39552 KB Output is correct
7 Correct 26 ms 43256 KB Output is correct
8 Correct 51 ms 55416 KB Output is correct
9 Correct 356 ms 208632 KB Output is correct
10 Correct 385 ms 209528 KB Output is correct
11 Correct 305 ms 203896 KB Output is correct
12 Correct 131 ms 104568 KB Output is correct
13 Correct 481 ms 209016 KB Output is correct
14 Correct 506 ms 209016 KB Output is correct
15 Correct 269 ms 204024 KB Output is correct
16 Correct 251 ms 204920 KB Output is correct
17 Correct 179 ms 132088 KB Output is correct
18 Correct 139 ms 107128 KB Output is correct

Subtask #2
17.7777777778 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 118648 KB Output is correct
2 Correct 226 ms 127688 KB Output is correct
3 Correct 785 ms 210168 KB Output is correct
4 Correct 233 ms 152696 KB Output is correct
5 Correct 671 ms 207864 KB Output is correct
6 Correct 230 ms 178040 KB Output is correct
7 Correct 195 ms 118648 KB Output is correct
8 Correct 208 ms 146680 KB Output is correct
9 Correct 681 ms 210032 KB Output is correct
10 Correct 799 ms 210168 KB Output is correct
11 Incorrect 792 ms 210080 KB Output isn't correct
12 Correct 374 ms 206328 KB Output is correct
13 Correct 178 ms 128888 KB Output is correct
14 Correct 217 ms 152568 KB Output is correct
15 Correct 683 ms 211096 KB Output is correct
16 Correct 206 ms 127608 KB Output is correct
17 Incorrect 485 ms 209100 KB Output isn't correct
18 Correct 821 ms 210760 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 851 ms 210376 KB Output isn't correct
2 Incorrect 816 ms 210200 KB Output isn't correct
3 Incorrect 873 ms 209992 KB Output isn't correct
4 Correct 582 ms 207992 KB Output is correct
5 Correct 457 ms 127644 KB Output is correct
6 Correct 764 ms 211320 KB Output is correct
7 Correct 753 ms 204664 KB Output is correct
8 Incorrect 926 ms 210296 KB Output isn't correct
9 Incorrect 899 ms 210308 KB Output isn't correct
10 Correct 448 ms 203768 KB Output is correct
11 Correct 354 ms 188408 KB Output is correct
12 Correct 587 ms 210936 KB Output is correct
13 Correct 954 ms 210168 KB Output is correct
14 Correct 607 ms 210812 KB Output is correct
15 Incorrect 560 ms 209784 KB Output isn't correct
16 Incorrect 584 ms 208856 KB Output isn't correct
17 Correct 745 ms 208760 KB Output is correct
18 Incorrect 761 ms 210040 KB Output isn't correct
19 Correct 286 ms 151416 KB Output is correct
20 Execution timed out 1010 ms 209912 KB Time limit exceeded
21 Correct 664 ms 212344 KB Output is correct
22 Execution timed out 1103 ms 211064 KB Time limit exceeded
23 Correct 420 ms 131576 KB Output is correct
24 Correct 367 ms 121336 KB Output is correct
25 Correct 594 ms 206584 KB Output is correct
26 Correct 590 ms 207888 KB Output is correct
27 Execution timed out 1106 ms 210912 KB Time limit exceeded
28 Correct 386 ms 144376 KB Output is correct
29 Correct 990 ms 210604 KB Output is correct
30 Correct 958 ms 208928 KB Output is correct
31 Correct 441 ms 149240 KB Output is correct
32 Correct 440 ms 164904 KB Output is correct
33 Correct 321 ms 111352 KB Output is correct
34 Correct 600 ms 204664 KB Output is correct
35 Correct 404 ms 146936 KB Output is correct
36 Execution timed out 1118 ms 210168 KB Time limit exceeded
37 Correct 534 ms 127740 KB Output is correct
38 Correct 855 ms 211320 KB Output is correct
39 Correct 414 ms 127972 KB Output is correct
40 Correct 722 ms 209656 KB Output is correct
41 Correct 765 ms 207992 KB Output is correct
42 Incorrect 741 ms 208632 KB Output isn't correct