oj.uz

Submission #256320

# Submission time Handle Problem Language Result Execution time Memory
256320 2020-08-02T14:19:42 Z Saboon Brunhilda’s Birthday (BOI13_brunhilda) C++14
94.6032 / 100
 1000 ms 213972 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;
	while (m --){
		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;
	if (sz <= 20){
		ll tof = 1;
		for (int i = 0; i < sz; i++)
			if (tof < maxn)
				tof *= p[i];
		mxm = min(1ll*mxm, tof);
	}
	for (int i = 1; i < mxm; 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 ++;
		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:67: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 254 ms 204920 KB Output is correct
3 Correct 27 ms 43392 KB Output is correct
4 Correct 115 ms 107132 KB Output is correct
5 Correct 150 ms 131832 KB Output is correct
6 Correct 21 ms 39552 KB Output is correct
7 Correct 26 ms 43392 KB Output is correct
8 Correct 46 ms 55416 KB Output is correct
9 Correct 345 ms 208632 KB Output is correct
10 Correct 368 ms 209656 KB Output is correct
11 Correct 304 ms 203896 KB Output is correct
12 Correct 103 ms 104568 KB Output is correct
13 Correct 543 ms 212820 KB Output is correct
14 Correct 543 ms 212856 KB Output is correct
15 Correct 278 ms 204024 KB Output is correct
16 Correct 253 ms 204920 KB Output is correct
17 Correct 156 ms 132216 KB Output is correct
18 Correct 119 ms 107128 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 118648 KB Output is correct
2 Correct 236 ms 127384 KB Output is correct
3 Execution timed out 1064 ms 213972 KB Time limit exceeded
4 Correct 217 ms 152636 KB Output is correct
5 Correct 560 ms 208348 KB Output is correct
6 Correct 230 ms 177912 KB Output is correct
7 Correct 160 ms 118776 KB Output is correct
8 Correct 197 ms 146680 KB Output is correct
9 Correct 677 ms 210524 KB Output is correct
10 Correct 971 ms 213960 KB Output is correct
11 Correct 877 ms 213468 KB Output is correct
12 Correct 352 ms 206456 KB Output is correct
13 Correct 152 ms 128764 KB Output is correct
14 Correct 232 ms 152608 KB Output is correct
15 Correct 820 ms 212472 KB Output is correct
16 Correct 225 ms 127480 KB Output is correct
17 Correct 559 ms 212600 KB Output is correct
18 Correct 783 ms 211388 KB Output is correct

Subtask #3
55.7142857143 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 873 ms 213108 KB Output is correct
2 Correct 954 ms 213752 KB Output is correct
3 Correct 963 ms 213880 KB Output is correct
4 Correct 416 ms 208120 KB Output is correct
5 Correct 265 ms 127324 KB Output is correct
6 Correct 550 ms 211488 KB Output is correct
7 Correct 502 ms 204664 KB Output is correct
8 Correct 779 ms 213020 KB Output is correct
9 Correct 780 ms 212964 KB Output is correct
10 Correct 388 ms 203856 KB Output is correct
11 Correct 318 ms 188284 KB Output is correct
12 Correct 520 ms 211064 KB Output is correct
13 Correct 775 ms 212600 KB Output is correct
14 Correct 417 ms 211064 KB Output is correct
15 Correct 559 ms 212728 KB Output is correct
16 Correct 624 ms 213112 KB Output is correct
17 Correct 613 ms 208820 KB Output is correct
18 Correct 952 ms 213496 KB Output is correct
19 Correct 200 ms 151384 KB Output is correct
20 Correct 977 ms 213496 KB Output is correct
21 Correct 467 ms 212328 KB Output is correct
22 Execution timed out 1035 ms 213880 KB Time limit exceeded
23 Correct 262 ms 131320 KB Output is correct
24 Correct 196 ms 121080 KB Output is correct
25 Correct 451 ms 206584 KB Output is correct
26 Correct 427 ms 207864 KB Output is correct
27 Execution timed out 1101 ms 211388 KB Time limit exceeded
28 Correct 203 ms 144376 KB Output is correct
29 Correct 750 ms 210680 KB Output is correct
30 Correct 631 ms 208888 KB Output is correct
31 Correct 241 ms 149240 KB Output is correct
32 Correct 266 ms 164856 KB Output is correct
33 Correct 159 ms 111352 KB Output is correct
34 Correct 536 ms 204312 KB Output is correct
35 Correct 221 ms 146936 KB Output is correct
36 Execution timed out 1046 ms 213628 KB Time limit exceeded
37 Correct 284 ms 126968 KB Output is correct
38 Correct 631 ms 211344 KB Output is correct
39 Correct 234 ms 127896 KB Output is correct
40 Correct 526 ms 209656 KB Output is correct
41 Correct 551 ms 208168 KB Output is correct
42 Correct 607 ms 213468 KB Output is correct