Submission #734608

#TimeUsernameProblemLanguageResultExecution timeMemory
734608DAleksaBrunhilda’s Birthday (BOI13_brunhilda)C++17
97.78 / 100
507 ms195040 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e7 + 10; int n, q; vector<int> p; vector<int> v; int cnt[N]; 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.size() - 1; i >= 0; i--) { for(int j = p[i]; j < N; j += p[i]) { if(prime[j] == 0) { cnt[j]++; prime[j] = p[i]; } } } cnt[0]++; prime[0] = p.back(); for(int i = 0; i < N; i++) for(int j = 0; j < cnt[i]; j++) v.push_back(i); 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...