# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
631304 | 2022-08-18T03:01:17 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 ll 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 = 5; 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(5, 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 39380 KB | Output is correct |
2 | Correct | 535 ms | 117708 KB | Output is correct |
3 | Correct | 29 ms | 39380 KB | Output is correct |
4 | Correct | 475 ms | 117732 KB | Output is correct |
5 | Correct | 512 ms | 117744 KB | Output is correct |
6 | Correct | 24 ms | 39380 KB | Output is correct |
7 | Correct | 32 ms | 39464 KB | Output is correct |
8 | Correct | 62 ms | 46484 KB | Output is correct |
9 | Correct | 602 ms | 117664 KB | Output is correct |
10 | Correct | 691 ms | 117756 KB | Output is correct |
11 | Correct | 640 ms | 117764 KB | Output is correct |
12 | Correct | 444 ms | 117760 KB | Output is correct |
13 | Execution timed out | 1045 ms | 117904 KB | Time limit exceeded |
14 | Execution timed out | 1100 ms | 117744 KB | Time limit exceeded |
15 | Correct | 563 ms | 117768 KB | Output is correct |
16 | Correct | 550 ms | 117732 KB | Output is correct |
17 | Correct | 585 ms | 117656 KB | Output is correct |
18 | Correct | 474 ms | 117820 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 591 ms | 122432 KB | Output is correct |
2 | Correct | 653 ms | 160656 KB | Output is correct |
3 | Execution timed out | 1092 ms | 104692 KB | Time limit exceeded |
4 | Correct | 604 ms | 118348 KB | Output is correct |
5 | Execution timed out | 1089 ms | 126512 KB | Time limit exceeded |
6 | Correct | 534 ms | 118116 KB | Output is correct |
7 | Correct | 579 ms | 122288 KB | Output is correct |
8 | Correct | 594 ms | 117892 KB | Output is correct |
9 | Execution timed out | 1099 ms | 118200 KB | Time limit exceeded |
10 | Execution timed out | 1092 ms | 106928 KB | Time limit exceeded |
11 | Execution timed out | 1092 ms | 105736 KB | Time limit exceeded |
12 | Correct | 686 ms | 117976 KB | Output is correct |
13 | Correct | 527 ms | 119928 KB | Output is correct |
14 | Correct | 595 ms | 118280 KB | Output is correct |
15 | Execution timed out | 1092 ms | 114716 KB | Time limit exceeded |
16 | Correct | 667 ms | 160736 KB | Output is correct |
17 | Execution timed out | 1045 ms | 118240 KB | Time limit exceeded |
18 | Execution timed out | 1080 ms | 134820 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1078 ms | 117308 KB | Time limit exceeded |
2 | Execution timed out | 1095 ms | 100744 KB | Time limit exceeded |
3 | Execution timed out | 1096 ms | 105184 KB | Time limit exceeded |
4 | Correct | 765 ms | 118580 KB | Output is correct |
5 | Correct | 752 ms | 142764 KB | Output is correct |
6 | Execution timed out | 1027 ms | 119016 KB | Time limit exceeded |
7 | Execution timed out | 1103 ms | 136096 KB | Time limit exceeded |
8 | Execution timed out | 1094 ms | 115400 KB | Time limit exceeded |
9 | Execution timed out | 1093 ms | 116660 KB | Time limit exceeded |
10 | Correct | 843 ms | 118468 KB | Output is correct |
11 | Correct | 706 ms | 118620 KB | Output is correct |
12 | Correct | 968 ms | 118640 KB | Output is correct |
13 | Execution timed out | 1095 ms | 106428 KB | Time limit exceeded |
14 | Correct | 768 ms | 118200 KB | Output is correct |
15 | Execution timed out | 1034 ms | 118476 KB | Time limit exceeded |
16 | Execution timed out | 1095 ms | 116436 KB | Time limit exceeded |
17 | Execution timed out | 1092 ms | 121004 KB | Time limit exceeded |
18 | Execution timed out | 1093 ms | 103060 KB | Time limit exceeded |
19 | Correct | 548 ms | 121212 KB | Output is correct |
20 | Execution timed out | 1085 ms | 103708 KB | Time limit exceeded |
21 | Correct | 874 ms | 118344 KB | Output is correct |
22 | Execution timed out | 1073 ms | 108520 KB | Time limit exceeded |
23 | Correct | 754 ms | 123988 KB | Output is correct |
24 | Correct | 550 ms | 118476 KB | Output is correct |
25 | Correct | 816 ms | 118364 KB | Output is correct |
26 | Correct | 837 ms | 118548 KB | Output is correct |
27 | Execution timed out | 1094 ms | 98912 KB | Time limit exceeded |
28 | Correct | 578 ms | 118812 KB | Output is correct |
29 | Execution timed out | 1091 ms | 109252 KB | Time limit exceeded |
30 | Execution timed out | 1091 ms | 106652 KB | Time limit exceeded |
31 | Correct | 644 ms | 119408 KB | Output is correct |
32 | Correct | 733 ms | 118588 KB | Output is correct |
33 | Correct | 532 ms | 119028 KB | Output is correct |
34 | Execution timed out | 1085 ms | 134788 KB | Time limit exceeded |
35 | Correct | 673 ms | 118892 KB | Output is correct |
36 | Execution timed out | 1083 ms | 107668 KB | Time limit exceeded |
37 | Correct | 781 ms | 142756 KB | Output is correct |
38 | Execution timed out | 1077 ms | 116800 KB | Time limit exceeded |
39 | Correct | 643 ms | 118648 KB | Output is correct |
40 | Correct | 941 ms | 119404 KB | Output is correct |
41 | Execution timed out | 1089 ms | 154692 KB | Time limit exceeded |
42 | Execution timed out | 1095 ms | 112596 KB | Time limit exceeded |