| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 631307 | 2022-08-18T03:03:01 Z | TranGiaHuy1508 | Brunhilda’s Birthday (BOI13_brunhilda) | C++17 | 1000 ms | 160736 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];
vector<int> *divs[maxval];
void main_program(){
int m, Q; cin >> m >> Q;
vi v(m); cin >> v; sort(all(v));
divs[0] = new vector<int>;
for (int i = 3; i < m; i++) divs[0]->push_back(v[i]);
for (int i = 0; i < maxval; i++){
dp[i] = inf;
}
queue<int> q;
dp[0] = 0; q.push(0);
int lim = 1;
while (!q.empty()){
int x = q.front(); q.pop();
for (int i = 0; i < min(3, m); i++){
if (x % v[i] == 0){
while (lim < min(x + v[i], maxval)){
dp[lim] = dp[x] + 1; q.push(lim);
lim++;
}
}
}
if (divs[x]){
for (auto i: *divs[x]){
while (lim < min(x + i, maxval)){
dp[lim] = dp[x] + 1; q.push(lim);
lim++;
}
if (x + i < maxval){
if (!divs[x + i]) divs[x + i] = new vector<int>;
divs[x + i]->push_back(i);
}
}
delete divs[x];
}
}
for (int i = 0; i < Q; i++){
int x; cin >> x;
if (dp[x] == inf) cout << "oo\n";
else cout << dp[x] << "\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 | 20 ms | 39380 KB | Output is correct |
| 2 | Correct | 479 ms | 117632 KB | Output is correct |
| 3 | Correct | 30 ms | 41428 KB | Output is correct |
| 4 | Correct | 436 ms | 117708 KB | Output is correct |
| 5 | Correct | 448 ms | 117644 KB | Output is correct |
| 6 | Correct | 26 ms | 39452 KB | Output is correct |
| 7 | Correct | 37 ms | 41448 KB | Output is correct |
| 8 | Correct | 60 ms | 46464 KB | Output is correct |
| 9 | Correct | 630 ms | 117676 KB | Output is correct |
| 10 | Correct | 712 ms | 117788 KB | Output is correct |
| 11 | Correct | 638 ms | 117608 KB | Output is correct |
| 12 | Correct | 389 ms | 117712 KB | Output is correct |
| 13 | Execution timed out | 1079 ms | 110408 KB | Time limit exceeded |
| 14 | Execution timed out | 1077 ms | 110392 KB | Time limit exceeded |
| 15 | Correct | 608 ms | 117624 KB | Output is correct |
| 16 | Correct | 533 ms | 117740 KB | Output is correct |
| 17 | Correct | 447 ms | 117684 KB | Output is correct |
| 18 | Correct | 356 ms | 117656 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 555 ms | 122324 KB | Output is correct |
| 2 | Correct | 633 ms | 160668 KB | Output is correct |
| 3 | Execution timed out | 1107 ms | 102812 KB | Time limit exceeded |
| 4 | Correct | 599 ms | 118356 KB | Output is correct |
| 5 | Execution timed out | 1072 ms | 123876 KB | Time limit exceeded |
| 6 | Correct | 477 ms | 118024 KB | Output is correct |
| 7 | Correct | 578 ms | 122288 KB | Output is correct |
| 8 | Correct | 521 ms | 117908 KB | Output is correct |
| 9 | Execution timed out | 1058 ms | 110604 KB | Time limit exceeded |
| 10 | Execution timed out | 1085 ms | 101504 KB | Time limit exceeded |
| 11 | Execution timed out | 1090 ms | 101916 KB | Time limit exceeded |
| 12 | Correct | 648 ms | 118008 KB | Output is correct |
| 13 | Correct | 428 ms | 119956 KB | Output is correct |
| 14 | Correct | 521 ms | 118368 KB | Output is correct |
| 15 | Execution timed out | 1099 ms | 112780 KB | Time limit exceeded |
| 16 | Correct | 591 ms | 160736 KB | Output is correct |
| 17 | Execution timed out | 1100 ms | 117732 KB | Time limit exceeded |
| 18 | Execution timed out | 1101 ms | 129696 KB | Time limit exceeded |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1066 ms | 108024 KB | Time limit exceeded |
| 2 | Execution timed out | 1100 ms | 98016 KB | Time limit exceeded |
| 3 | Execution timed out | 1092 ms | 92720 KB | Time limit exceeded |
| 4 | Correct | 737 ms | 118636 KB | Output is correct |
| 5 | Correct | 639 ms | 142812 KB | Output is correct |
| 6 | Execution timed out | 1091 ms | 119052 KB | Time limit exceeded |
| 7 | Execution timed out | 1094 ms | 136200 KB | Time limit exceeded |
| 8 | Execution timed out | 1091 ms | 112364 KB | Time limit exceeded |
| 9 | Execution timed out | 1072 ms | 112364 KB | Time limit exceeded |
| 10 | Correct | 749 ms | 118568 KB | Output is correct |
| 11 | Correct | 692 ms | 118436 KB | Output is correct |
| 12 | Correct | 970 ms | 118528 KB | Output is correct |
| 13 | Execution timed out | 1098 ms | 107692 KB | Time limit exceeded |
| 14 | Correct | 702 ms | 118252 KB | Output is correct |
| 15 | Execution timed out | 1097 ms | 118480 KB | Time limit exceeded |
| 16 | Execution timed out | 1101 ms | 112128 KB | Time limit exceeded |
| 17 | Execution timed out | 1099 ms | 120932 KB | Time limit exceeded |
| 18 | Execution timed out | 1089 ms | 100168 KB | Time limit exceeded |
| 19 | Correct | 450 ms | 121036 KB | Output is correct |
| 20 | Execution timed out | 1092 ms | 105320 KB | Time limit exceeded |
| 21 | Correct | 860 ms | 118532 KB | Output is correct |
| 22 | Execution timed out | 1095 ms | 104232 KB | Time limit exceeded |
| 23 | Correct | 597 ms | 124008 KB | Output is correct |
| 24 | Correct | 407 ms | 118468 KB | Output is correct |
| 25 | Correct | 734 ms | 118524 KB | Output is correct |
| 26 | Correct | 683 ms | 118560 KB | Output is correct |
| 27 | Execution timed out | 1094 ms | 105212 KB | Time limit exceeded |
| 28 | Correct | 423 ms | 118876 KB | Output is correct |
| 29 | Execution timed out | 1088 ms | 112212 KB | Time limit exceeded |
| 30 | Execution timed out | 1097 ms | 112992 KB | Time limit exceeded |
| 31 | Correct | 486 ms | 119496 KB | Output is correct |
| 32 | Correct | 499 ms | 118616 KB | Output is correct |
| 33 | Correct | 367 ms | 118860 KB | Output is correct |
| 34 | Execution timed out | 1074 ms | 136132 KB | Time limit exceeded |
| 35 | Correct | 438 ms | 118820 KB | Output is correct |
| 36 | Execution timed out | 1075 ms | 110556 KB | Time limit exceeded |
| 37 | Correct | 622 ms | 142828 KB | Output is correct |
| 38 | Correct | 953 ms | 119140 KB | Output is correct |
| 39 | Correct | 419 ms | 118604 KB | Output is correct |
| 40 | Correct | 878 ms | 119480 KB | Output is correct |
| 41 | Execution timed out | 1058 ms | 154716 KB | Time limit exceeded |
| 42 | Execution timed out | 1097 ms | 118448 KB | Time limit exceeded |