#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define pdb pair <double, double>
#define YES cout<<"YES"
#define NO cout<<"NO"
#define endl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll>
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;
const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const ll N=1e5, MAXN=1e7;
ll n, q;
ll a[N+5];
ll ans[MAXN+5];
ll product=1;
void input()
{
cin >> n >> q;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
product*=a[i];
if(product>=MAXN) product=MAXN;
}
}
void solve()
{
ll cur=n;
for(int i = 2; i <= MAXN; i++)
{
ans[i]=INFINF;
if(i>=product) continue;
if(i<a[n])
{
ans[i]=1;
continue;
}
for(int j = n; j >= 1 && j >= n-4; j--)
{
if(i%a[j]) ans[i]=min(ans[i], ans[i-i%a[j]]+1);
}
for(int j = n-5; j >= 1; j--)
{
if(i%a[j])
{
ans[i]=min(ans[i], ans[i-i%a[j]]+1);
break;
}
}
}
while(q--)
{
ll x;
cin >> x;
if(ans[x]==INFINF) cout << "oo";
else cout << ans[x];
endl;
}
}
int main()
{
// auto start_time = chrono::high_resolution_clock::now();
// freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
input();
solve();
// auto end_time = chrono::high_resolution_clock::now();
// double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
// cout << "\n[ " << duration << " ms ]\n";
}
Compilation message
brunhilda.cpp: In function 'void solve()':
brunhilda.cpp:41:5: warning: unused variable 'cur' [-Wunused-variable]
41 | ll cur=n;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
78540 KB |
Output is correct |
2 |
Incorrect |
445 ms |
78488 KB |
Output isn't correct |
3 |
Correct |
43 ms |
78548 KB |
Output is correct |
4 |
Incorrect |
394 ms |
78600 KB |
Output isn't correct |
5 |
Correct |
473 ms |
78620 KB |
Output is correct |
6 |
Correct |
33 ms |
78540 KB |
Output is correct |
7 |
Correct |
48 ms |
78492 KB |
Output is correct |
8 |
Correct |
75 ms |
78592 KB |
Output is correct |
9 |
Correct |
489 ms |
78552 KB |
Output is correct |
10 |
Correct |
476 ms |
78540 KB |
Output is correct |
11 |
Incorrect |
460 ms |
78476 KB |
Output isn't correct |
12 |
Correct |
402 ms |
78532 KB |
Output is correct |
13 |
Correct |
394 ms |
78588 KB |
Output is correct |
14 |
Incorrect |
383 ms |
78540 KB |
Output isn't correct |
15 |
Incorrect |
465 ms |
78668 KB |
Output isn't correct |
16 |
Incorrect |
423 ms |
78492 KB |
Output isn't correct |
17 |
Incorrect |
456 ms |
78520 KB |
Output isn't correct |
18 |
Incorrect |
393 ms |
78668 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
312 ms |
78624 KB |
Output is correct |
2 |
Correct |
72 ms |
79224 KB |
Output is correct |
3 |
Correct |
253 ms |
79068 KB |
Output is correct |
4 |
Incorrect |
350 ms |
78568 KB |
Output isn't correct |
5 |
Correct |
312 ms |
78880 KB |
Output is correct |
6 |
Incorrect |
350 ms |
78544 KB |
Output isn't correct |
7 |
Correct |
325 ms |
78668 KB |
Output is correct |
8 |
Incorrect |
373 ms |
78604 KB |
Output isn't correct |
9 |
Correct |
308 ms |
79096 KB |
Output is correct |
10 |
Correct |
256 ms |
79052 KB |
Output is correct |
11 |
Incorrect |
321 ms |
78828 KB |
Output isn't correct |
12 |
Incorrect |
355 ms |
78596 KB |
Output isn't correct |
13 |
Incorrect |
331 ms |
78568 KB |
Output isn't correct |
14 |
Incorrect |
350 ms |
78484 KB |
Output isn't correct |
15 |
Correct |
312 ms |
78816 KB |
Output is correct |
16 |
Correct |
78 ms |
79180 KB |
Output is correct |
17 |
Correct |
358 ms |
78508 KB |
Output is correct |
18 |
Incorrect |
183 ms |
79332 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
324 ms |
79040 KB |
Output isn't correct |
2 |
Incorrect |
324 ms |
78964 KB |
Output isn't correct |
3 |
Correct |
310 ms |
79140 KB |
Output is correct |
4 |
Incorrect |
377 ms |
79044 KB |
Output isn't correct |
5 |
Correct |
230 ms |
79540 KB |
Output is correct |
6 |
Incorrect |
387 ms |
79032 KB |
Output isn't correct |
7 |
Correct |
252 ms |
79416 KB |
Output is correct |
8 |
Incorrect |
327 ms |
79052 KB |
Output isn't correct |
9 |
Incorrect |
305 ms |
78976 KB |
Output isn't correct |
10 |
Incorrect |
355 ms |
78552 KB |
Output isn't correct |
11 |
Incorrect |
380 ms |
78628 KB |
Output isn't correct |
12 |
Incorrect |
347 ms |
78716 KB |
Output isn't correct |
13 |
Incorrect |
335 ms |
79084 KB |
Output isn't correct |
14 |
Incorrect |
470 ms |
79052 KB |
Output isn't correct |
15 |
Incorrect |
364 ms |
78668 KB |
Output isn't correct |
16 |
Incorrect |
357 ms |
78600 KB |
Output isn't correct |
17 |
Incorrect |
311 ms |
78900 KB |
Output isn't correct |
18 |
Incorrect |
318 ms |
79148 KB |
Output isn't correct |
19 |
Incorrect |
325 ms |
78780 KB |
Output isn't correct |
20 |
Correct |
322 ms |
79148 KB |
Output is correct |
21 |
Incorrect |
449 ms |
79168 KB |
Output isn't correct |
22 |
Incorrect |
310 ms |
79576 KB |
Output isn't correct |
23 |
Incorrect |
335 ms |
78992 KB |
Output isn't correct |
24 |
Incorrect |
375 ms |
78776 KB |
Output isn't correct |
25 |
Incorrect |
444 ms |
78940 KB |
Output isn't correct |
26 |
Incorrect |
372 ms |
78808 KB |
Output isn't correct |
27 |
Correct |
299 ms |
79404 KB |
Output is correct |
28 |
Incorrect |
356 ms |
79012 KB |
Output isn't correct |
29 |
Incorrect |
340 ms |
79496 KB |
Output isn't correct |
30 |
Incorrect |
323 ms |
79376 KB |
Output isn't correct |
31 |
Incorrect |
365 ms |
78788 KB |
Output isn't correct |
32 |
Incorrect |
370 ms |
78848 KB |
Output isn't correct |
33 |
Incorrect |
374 ms |
78780 KB |
Output isn't correct |
34 |
Correct |
245 ms |
79396 KB |
Output is correct |
35 |
Incorrect |
376 ms |
78896 KB |
Output isn't correct |
36 |
Incorrect |
306 ms |
79472 KB |
Output isn't correct |
37 |
Correct |
233 ms |
79464 KB |
Output is correct |
38 |
Incorrect |
370 ms |
78908 KB |
Output isn't correct |
39 |
Incorrect |
386 ms |
78796 KB |
Output isn't correct |
40 |
Incorrect |
356 ms |
78844 KB |
Output isn't correct |
41 |
Correct |
126 ms |
79360 KB |
Output is correct |
42 |
Incorrect |
407 ms |
79008 KB |
Output isn't correct |