| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 631356 | 2022-08-18T03:39:51 Z | TranGiaHuy1508 | Brunhilda’s Birthday (BOI13_brunhilda) | C++17 | 511 ms | 87736 KB |
/*
Unknown's C++ Template (v3.2)
*/
#include "bits/stdc++.h"
using namespace std;
// #define int long long
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mid ((l+r)>>1)
#define fi first
#define se second
#ifdef LOCAL
#define debug(x) cout << #x << " = " << x << "\n";
#else
#define debug(x) ;
#endif
template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x)
{ out << "(" << x.first << ", " << x.second << ")"; return out; }
template <class T>
ostream& operator << (ostream& out, vector<T> x){
out << "[";
for (int i=0; i<sz(x); i++) { out << (i ? ", " : "") << x[i]; }
out << "]"; return out;
}
template <class T>
istream& operator >> (istream& in, vector<T> &x){
for (auto &i: x) in >> i;
return in;
}
const ld PI = acos(-1.0);
const int allmod[3] = {(int)1e9+7, 998244353, (int)1e9+9};
const int mod = allmod[0];
const int maxn = 2e5 + 64;
const int inf = 1e9;
const ld eps = 1e-6;
const int multitest = 0;
const int maxval = 1e7 + 10;
int dp[maxval];
bool v[maxval];
int divs[maxval];
vi primes, inp;
void sieve(){
for (auto i: inp){
for (int j = 0; j < maxval; j += i) divs[j] = i;
}
}
#define chkmin(a, b) ((a) < (b) ? (a) : (b))
void main_program(){
int m, Q; cin >> m >> Q;
inp.resize(m); cin >> inp; sort(all(inp));
for (int i = 0; i < m; i++){
int x = inp[i]; v[x] = true;
}
sieve();
for (int i = 0; i < maxval; i++){
dp[i] = inf;
}
dp[0] = 0;
int x = 0;
int lim = 1;
while (x < maxval && lim < maxval){
if (x >= lim) break;
int j = x;
while (divs[j]){
int p = divs[j];
if (!p) break;
if (v[p]){
while (lim < chkmin(maxval, x + p)){
dp[lim] = dp[x] + 1;
// if (lim <= 10) cout << lim << " " << dp[lim] << "\n";
lim++;
}
}
j /= p;
if (!j) break;
}
x++;
}
// cout << lim << "\n";
for (int i = 0; i < Q; i++){
int a; cin >> a;
if (a >= lim) cout << "oo\n";
else cout << dp[a] << "\n";
}
}
void pre_main(){
}
signed main(){
#ifdef LOCAL
auto stime = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
if (fopen(".inp", "r")){
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
#endif
int t = 1; if (multitest) cin >> t;
pre_main();
while (t--) main_program();
#ifdef LOCAL
auto etime = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(etime-stime).count();
cout << "\n[" << duration << "ms]\n";
#endif
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 40 ms | 78540 KB | Output is correct |
| 2 | Correct | 263 ms | 78588 KB | Output is correct |
| 3 | Correct | 52 ms | 78484 KB | Output is correct |
| 4 | Correct | 69 ms | 78500 KB | Output is correct |
| 5 | Correct | 114 ms | 78584 KB | Output is correct |
| 6 | Correct | 41 ms | 78584 KB | Output is correct |
| 7 | Correct | 53 ms | 78548 KB | Output is correct |
| 8 | Correct | 69 ms | 78584 KB | Output is correct |
| 9 | Correct | 366 ms | 78584 KB | Output is correct |
| 10 | Correct | 384 ms | 78592 KB | Output is correct |
| 11 | Correct | 279 ms | 78588 KB | Output is correct |
| 12 | Correct | 62 ms | 78584 KB | Output is correct |
| 13 | Correct | 509 ms | 78604 KB | Output is correct |
| 14 | Correct | 502 ms | 78604 KB | Output is correct |
| 15 | Correct | 264 ms | 78664 KB | Output is correct |
| 16 | Correct | 253 ms | 78500 KB | Output is correct |
| 17 | Correct | 107 ms | 78504 KB | Output is correct |
| 18 | Correct | 67 ms | 78528 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 93 ms | 79516 KB | Output is correct |
| 2 | Correct | 87 ms | 87696 KB | Output is correct |
| 3 | Correct | 466 ms | 79768 KB | Output is correct |
| 4 | Correct | 141 ms | 78740 KB | Output is correct |
| 5 | Correct | 292 ms | 79976 KB | Output is correct |
| 6 | Correct | 186 ms | 78668 KB | Output is correct |
| 7 | Correct | 95 ms | 79516 KB | Output is correct |
| 8 | Correct | 141 ms | 78624 KB | Output is correct |
| 9 | Correct | 307 ms | 80052 KB | Output is correct |
| 10 | Correct | 495 ms | 79760 KB | Output is correct |
| 11 | Correct | 472 ms | 79160 KB | Output is correct |
| 12 | Correct | 298 ms | 78688 KB | Output is correct |
| 13 | Correct | 88 ms | 79096 KB | Output is correct |
| 14 | Correct | 143 ms | 78676 KB | Output is correct |
| 15 | Correct | 438 ms | 79444 KB | Output is correct |
| 16 | Correct | 100 ms | 87736 KB | Output is correct |
| 17 | Correct | 474 ms | 78636 KB | Output is correct |
| 18 | Correct | 326 ms | 80856 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 457 ms | 79772 KB | Output is correct |
| 2 | Correct | 498 ms | 79524 KB | Output is correct |
| 3 | Correct | 495 ms | 79572 KB | Output is correct |
| 4 | Correct | 355 ms | 78956 KB | Output is correct |
| 5 | Correct | 114 ms | 83524 KB | Output is correct |
| 6 | Correct | 499 ms | 79004 KB | Output is correct |
| 7 | Correct | 247 ms | 81244 KB | Output is correct |
| 8 | Correct | 475 ms | 79776 KB | Output is correct |
| 9 | Correct | 448 ms | 79820 KB | Output is correct |
| 10 | Correct | 313 ms | 78668 KB | Output is correct |
| 11 | Correct | 220 ms | 78704 KB | Output is correct |
| 12 | Correct | 463 ms | 78708 KB | Output is correct |
| 13 | Correct | 511 ms | 79360 KB | Output is correct |
| 14 | Correct | 445 ms | 79140 KB | Output is correct |
| 15 | Correct | 490 ms | 78688 KB | Output is correct |
| 16 | Correct | 494 ms | 78792 KB | Output is correct |
| 17 | Correct | 319 ms | 79560 KB | Output is correct |
| 18 | Correct | 491 ms | 79516 KB | Output is correct |
| 19 | Correct | 133 ms | 79296 KB | Output is correct |
| 20 | Correct | 497 ms | 79604 KB | Output is correct |
| 21 | Correct | 484 ms | 79104 KB | Output is correct |
| 22 | Correct | 502 ms | 80588 KB | Output is correct |
| 23 | Correct | 138 ms | 79912 KB | Output is correct |
| 24 | Correct | 110 ms | 78944 KB | Output is correct |
| 25 | Correct | 320 ms | 78888 KB | Output is correct |
| 26 | Correct | 349 ms | 78864 KB | Output is correct |
| 27 | Correct | 472 ms | 80308 KB | Output is correct |
| 28 | Correct | 127 ms | 78952 KB | Output is correct |
| 29 | Correct | 311 ms | 80588 KB | Output is correct |
| 30 | Correct | 276 ms | 80028 KB | Output is correct |
| 31 | Correct | 153 ms | 79028 KB | Output is correct |
| 32 | Correct | 192 ms | 78972 KB | Output is correct |
| 33 | Correct | 96 ms | 78936 KB | Output is correct |
| 34 | Correct | 223 ms | 81352 KB | Output is correct |
| 35 | Correct | 160 ms | 78952 KB | Output is correct |
| 36 | Correct | 475 ms | 80676 KB | Output is correct |
| 37 | Correct | 117 ms | 83476 KB | Output is correct |
| 38 | Correct | 466 ms | 79004 KB | Output is correct |
| 39 | Correct | 118 ms | 78972 KB | Output is correct |
| 40 | Correct | 380 ms | 78996 KB | Output is correct |
| 41 | Correct | 266 ms | 82260 KB | Output is correct |
| 42 | Correct | 487 ms | 79048 KB | Output is correct |