#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';
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
