Submission #155731

#TimeUsernameProblemLanguageResultExecution timeMemory
155731Flying_dragon_02Brunhilda’s Birthday (BOI13_brunhilda)C++14
28.57 / 100
1100 ms158056 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; const int mod = 1e9 + 7; const int inf = 1e9; int add(int x, int y) { return (1ll * x + 1ll * y) % mod; } int del(int x, int y) { return ((1ll * x - 1ll * y) % mod + mod) % mod; } int mul(int x, int y) { return (1ll * x * 1ll * y) % mod; } const int N = 1e7 + 5; int dp[2 * N], p[N]; bool used[N]; int bit[2 * N]; void update(int x, int val) { while(x > 0) { bit[x] = min(bit[x], val); x -= x & (-x); } } int get(int x) { if(x == 0) return 0; int val = inf; while(x < N) { val = min(val, bit[x]); x += x & (-x); } return val; } int m, q; int main() { cin.tie(0), ios_base::sync_with_stdio(0); cin >> m >> q; for(int i = 0; i < N; i++) p[i] = inf; for(int i = 1; i <= N - 5; i++) bit[i] = dp[i] = inf; for(int i = 1; i <= m; i++) { int x; cin >> x; if(used[x]) continue; used[x] = 1; dp[x - 1] = 1; for(int l = 0; l < N; l++) { if(x * l >= N) break; p[x * l] = min(p[x * l], x); } } for(int i = N - 6; i >= 0; i--) dp[i] = min(dp[i + 1], dp[i]); for(int i = 1; i <= N - 5; i++) { dp[i] = min(dp[i], get(i)); int num = i; while(1) { if(num % p[num] != 0) break; update(i + p[num] - 1, dp[i] + 1); int y = p[num]; while(num % y == 0) num /= y; } } for(int i = 1; i <= q; i++) { 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...