#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);
for (int i = 0; i < m; i++){
int x;
cin >> x;
if (mark[x])
continue;
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]];
}
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 |
24 ms |
39552 KB |
Output is correct |
| 2 |
Correct |
253 ms |
204920 KB |
Output is correct |
| 3 |
Correct |
28 ms |
43256 KB |
Output is correct |
| 4 |
Correct |
150 ms |
107256 KB |
Output is correct |
| 5 |
Correct |
147 ms |
131868 KB |
Output is correct |
| 6 |
Correct |
25 ms |
39552 KB |
Output is correct |
| 7 |
Correct |
25 ms |
43264 KB |
Output is correct |
| 8 |
Correct |
46 ms |
55416 KB |
Output is correct |
| 9 |
Correct |
336 ms |
208632 KB |
Output is correct |
| 10 |
Correct |
391 ms |
209564 KB |
Output is correct |
| 11 |
Correct |
308 ms |
203904 KB |
Output is correct |
| 12 |
Correct |
98 ms |
104568 KB |
Output is correct |
| 13 |
Correct |
471 ms |
208888 KB |
Output is correct |
| 14 |
Correct |
489 ms |
209144 KB |
Output is correct |
| 15 |
Correct |
264 ms |
204152 KB |
Output is correct |
| 16 |
Correct |
267 ms |
204920 KB |
Output is correct |
| 17 |
Correct |
156 ms |
132216 KB |
Output is correct |
| 18 |
Correct |
143 ms |
107128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
193 ms |
118776 KB |
Output is correct |
| 2 |
Incorrect |
248 ms |
127736 KB |
Output isn't correct |
| 3 |
Incorrect |
852 ms |
210936 KB |
Output isn't correct |
| 4 |
Correct |
223 ms |
152660 KB |
Output is correct |
| 5 |
Correct |
738 ms |
208284 KB |
Output is correct |
| 6 |
Correct |
245 ms |
177904 KB |
Output is correct |
| 7 |
Correct |
165 ms |
118904 KB |
Output is correct |
| 8 |
Correct |
192 ms |
146552 KB |
Output is correct |
| 9 |
Incorrect |
849 ms |
210552 KB |
Output isn't correct |
| 10 |
Incorrect |
793 ms |
210656 KB |
Output isn't correct |
| 11 |
Incorrect |
735 ms |
210424 KB |
Output isn't correct |
| 12 |
Correct |
383 ms |
206460 KB |
Output is correct |
| 13 |
Correct |
154 ms |
128760 KB |
Output is correct |
| 14 |
Correct |
240 ms |
152696 KB |
Output is correct |
| 15 |
Correct |
813 ms |
211292 KB |
Output is correct |
| 16 |
Incorrect |
196 ms |
127864 KB |
Output isn't correct |
| 17 |
Incorrect |
485 ms |
208988 KB |
Output isn't correct |
| 18 |
Incorrect |
799 ms |
211320 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
817 ms |
211004 KB |
Output isn't correct |
| 2 |
Incorrect |
801 ms |
210680 KB |
Output isn't correct |
| 3 |
Incorrect |
872 ms |
210808 KB |
Output isn't correct |
| 4 |
Correct |
570 ms |
208248 KB |
Output is correct |
| 5 |
Incorrect |
482 ms |
128252 KB |
Output isn't correct |
| 6 |
Correct |
761 ms |
211832 KB |
Output is correct |
| 7 |
Incorrect |
628 ms |
205304 KB |
Output isn't correct |
| 8 |
Incorrect |
765 ms |
211064 KB |
Output isn't correct |
| 9 |
Incorrect |
758 ms |
210936 KB |
Output isn't correct |
| 10 |
Correct |
397 ms |
203896 KB |
Output is correct |
| 11 |
Correct |
341 ms |
188540 KB |
Output is correct |
| 12 |
Correct |
559 ms |
211192 KB |
Output is correct |
| 13 |
Correct |
886 ms |
211192 KB |
Output is correct |
| 14 |
Correct |
587 ms |
211192 KB |
Output is correct |
| 15 |
Incorrect |
565 ms |
209784 KB |
Output isn't correct |
| 16 |
Incorrect |
561 ms |
208892 KB |
Output isn't correct |
| 17 |
Correct |
709 ms |
209144 KB |
Output is correct |
| 18 |
Incorrect |
799 ms |
210680 KB |
Output isn't correct |
| 19 |
Correct |
264 ms |
151672 KB |
Output is correct |
| 20 |
Execution timed out |
1004 ms |
210680 KB |
Time limit exceeded |
| 21 |
Correct |
658 ms |
212600 KB |
Output is correct |
| 22 |
Execution timed out |
1057 ms |
212472 KB |
Time limit exceeded |
| 23 |
Correct |
451 ms |
132092 KB |
Output is correct |
| 24 |
Correct |
358 ms |
121592 KB |
Output is correct |
| 25 |
Correct |
586 ms |
206968 KB |
Output is correct |
| 26 |
Correct |
612 ms |
208120 KB |
Output is correct |
| 27 |
Correct |
906 ms |
212088 KB |
Output is correct |
| 28 |
Correct |
385 ms |
144472 KB |
Output is correct |
| 29 |
Execution timed out |
1084 ms |
210552 KB |
Time limit exceeded |
| 30 |
Incorrect |
860 ms |
209144 KB |
Output isn't correct |
| 31 |
Correct |
411 ms |
149244 KB |
Output is correct |
| 32 |
Correct |
442 ms |
164880 KB |
Output is correct |
| 33 |
Correct |
312 ms |
111352 KB |
Output is correct |
| 34 |
Incorrect |
588 ms |
204648 KB |
Output isn't correct |
| 35 |
Correct |
403 ms |
146936 KB |
Output is correct |
| 36 |
Incorrect |
968 ms |
211704 KB |
Output isn't correct |
| 37 |
Incorrect |
438 ms |
127932 KB |
Output isn't correct |
| 38 |
Correct |
749 ms |
211448 KB |
Output is correct |
| 39 |
Correct |
388 ms |
127992 KB |
Output is correct |
| 40 |
Correct |
709 ms |
209780 KB |
Output is correct |
| 41 |
Incorrect |
717 ms |
208120 KB |
Output isn't correct |
| 42 |
Incorrect |
701 ms |
209424 KB |
Output isn't correct |
