oj.uz

Submission #256311

# Submission time Handle Problem Language Result Execution time Memory
256311 2020-08-02T14:09:28 Z Saboon Brunhilda’s Birthday (BOI13_brunhilda) C++14
94.2857 / 100
 1000 ms 213880 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;
	scanf("%d%d", &m, &q);
	int sz = 0;
	memset(last, -1, sizeof last);
	int mxmp = 0;
	for (int i = 0; i < m; i++){
		int x;
		scanf("%d", &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;
		scanf("%d", &x);
		if (x >= mxm)
			printf("oo\n");
		else
			printf("%d\n", dp[x]);
	}
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
brunhilda.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39552 KB Output is correct
2 Correct 252 ms 204836 KB Output is correct
3 Correct 26 ms 43384 KB Output is correct
4 Correct 121 ms 107100 KB Output is correct
5 Correct 153 ms 131844 KB Output is correct
6 Correct 21 ms 39552 KB Output is correct
7 Correct 26 ms 43384 KB Output is correct
8 Correct 45 ms 55416 KB Output is correct
9 Correct 343 ms 208760 KB Output is correct
10 Correct 371 ms 209528 KB Output is correct
11 Correct 297 ms 203896 KB Output is correct
12 Correct 106 ms 104568 KB Output is correct
13 Correct 535 ms 212856 KB Output is correct
14 Correct 543 ms 212856 KB Output is correct
15 Correct 275 ms 204152 KB Output is correct
16 Correct 263 ms 205048 KB Output is correct
17 Correct 161 ms 132088 KB Output is correct
18 Correct 126 ms 107260 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 118648 KB Output is correct
2 Correct 217 ms 126840 KB Output is correct
3 Correct 970 ms 213628 KB Output is correct
4 Correct 215 ms 152568 KB Output is correct
5 Correct 580 ms 207992 KB Output is correct
6 Correct 226 ms 177912 KB Output is correct
7 Correct 162 ms 118620 KB Output is correct
8 Correct 199 ms 146552 KB Output is correct
9 Correct 690 ms 210120 KB Output is correct
10 Correct 955 ms 213548 KB Output is correct
11 Correct 891 ms 213112 KB Output is correct
12 Correct 360 ms 206328 KB Output is correct
13 Correct 158 ms 128760 KB Output is correct
14 Correct 220 ms 152568 KB Output is correct
15 Correct 766 ms 212216 KB Output is correct
16 Correct 242 ms 127104 KB Output is correct
17 Correct 581 ms 212452 KB Output is correct
18 Correct 816 ms 210964 KB Output is correct

Subtask #3
54.2857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 212992 KB Output is correct
2 Correct 967 ms 213496 KB Output is correct
3 Correct 934 ms 213624 KB Output is correct
4 Correct 422 ms 207912 KB Output is correct
5 Correct 260 ms 126968 KB Output is correct
6 Correct 556 ms 211704 KB Output is correct
7 Correct 501 ms 204536 KB Output is correct
8 Correct 786 ms 212856 KB Output is correct
9 Correct 896 ms 212984 KB Output is correct
10 Correct 383 ms 203812 KB Output is correct
11 Correct 317 ms 188280 KB Output is correct
12 Correct 512 ms 211192 KB Output is correct
13 Correct 812 ms 212600 KB Output is correct
14 Correct 421 ms 211192 KB Output is correct
15 Correct 591 ms 212728 KB Output is correct
16 Correct 615 ms 212984 KB Output is correct
17 Correct 635 ms 208888 KB Output is correct
18 Correct 988 ms 213396 KB Output is correct
19 Correct 203 ms 151420 KB Output is correct
20 Execution timed out 1033 ms 213492 KB Time limit exceeded
21 Correct 471 ms 212344 KB Output is correct
22 Execution timed out 1092 ms 213560 KB Time limit exceeded
23 Correct 317 ms 131416 KB Output is correct
24 Correct 196 ms 121208 KB Output is correct
25 Correct 430 ms 206712 KB Output is correct
26 Correct 415 ms 207992 KB Output is correct
27 Execution timed out 1104 ms 212228 KB Time limit exceeded
28 Correct 205 ms 144376 KB Output is correct
29 Correct 772 ms 210808 KB Output is correct
30 Correct 671 ms 208968 KB Output is correct
31 Correct 239 ms 149244 KB Output is correct
32 Correct 274 ms 164988 KB Output is correct
33 Correct 155 ms 111480 KB Output is correct
34 Correct 500 ms 204408 KB Output is correct
35 Correct 215 ms 147192 KB Output is correct
36 Execution timed out 1054 ms 213880 KB Time limit exceeded
37 Correct 264 ms 127096 KB Output is correct
38 Correct 552 ms 211452 KB Output is correct
39 Correct 195 ms 127992 KB Output is correct
40 Correct 497 ms 209784 KB Output is correct
41 Correct 531 ms 208120 KB Output is correct
42 Correct 602 ms 213452 KB Output is correct