oj.uz

답안 #256267

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

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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)