Submission #388565

#TimeUsernameProblemLanguageResultExecution timeMemory
388565Aryan_RainaBrunhilda’s Birthday (BOI13_brunhilda)C++14
100 / 100
329 ms157424 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define ar array const int INF = 1e17; const int MOD = 1e9 + 7; const int MXN = 1e7+9; int largestPrime[MXN], dp[MXN]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int m, q; cin>>m>>q; for (int i = 0; i < m; i++) { int p; cin>>p; for (int j = 0; j < MXN; j += p) largestPrime[j] = p; } int ind = 0; // represents the first index which is last multiple of some prime for (int i = 1; i < MXN; i++) { while (ind + largestPrime[ind] <= i || dp[ind] > INF/2) ind++; if (ind >= i) dp[i] = INF; else dp[i] = dp[ind] + 1; } while (q--) { int x; cin>>x; if (dp[x] > INF/2) cout<<"oo\n"; else cout<<dp[x]<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...