Submission #734601

#TimeUsernameProblemLanguageResultExecution timeMemory
734601DAleksaBrunhilda’s Birthday (BOI13_brunhilda)C++17
34.92 / 100
1096 ms171340 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e7 + 10; int n, q; vector<int> p; vector<int> v; int prime[N]; int prv[N]; int dp[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> q; p.resize(n); for(int i = 0; i < n; i++) cin >> p[i]; for(int i : p) { for(int j = i; j < N; j += i) { v.push_back(j); prime[j] = max(prime[j], i); } } v.push_back(0); prime[0] = p.back(); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); int j = 0; for(int i = 1; i < N; i++) { while(v[j] + prime[v[j]] <= i) j++; prv[i] = v[j]; } for(int i = 1; i < N; i++) { if(prv[i] == i) dp[i] = -1; else dp[i] = dp[prv[i]] + 1; } while(q--) { int x; cin >> x; if(dp[x] == -1) cout << "oo\n"; else cout << dp[x] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...