Submission #1247680

#TimeUsernameProblemLanguageResultExecution timeMemory
1247680arvindr9Brunhilda’s Birthday (BOI13_brunhilda)C++20
0 / 100
361 ms327680 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__) #else #define DEBUG(...) 6 #endif template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";} template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr> ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";} template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";} template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}} #define pi pair<int,int> #define mp make_pair #define pb push_back #define vi vector<int> #define eb emplace_back #define f first #define s second #define lep(i,a,b) for (int i = (a); i <= (b); i++) #define rep(i,a,b) for (int i = (a); i >= (b); i--) const int inf = 1e9; int t; const int mx = 1e7 + 5; vector<int> prime_divs[mx+1]; int trans[mx+1]; int dp[mx+1]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<int> primes; lep(i,1,n) { int x; cin >> x; primes.pb(x); } for (int x: primes) { for (int i = x; i < mx; i+=x) { prime_divs[i].pb(x); } } // initialize trans[mx] for (int p: primes) { int val = mx; val = min(val, mx-(mx%p)); trans[mx] = val; } rep(i,mx-1,0) { int val = trans[i+1]; for (int p: prime_divs[i+1]) { val = min(val, i-(i%p)); } trans[i] = val; } dp[0] = 0; lep(i,1,mx) { dp[i] = (i == trans[i]) ? inf : dp[trans[i]]+1; } lep(qq,1,q) { int x; cin >> x; if (dp[x] == inf) { 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...