Submission #491795

# Submission time Handle Problem Language Result Execution time Memory
491795 2021-12-04T13:13:47 Z Victor Brunhilda’s Birthday (BOI13_brunhilda) C++17
97.7778 / 100
424 ms 40576 KB
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int n, q, ans[10'000'001], rem;
priority_queue<ii> pq;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int p;
    ans[0] = 0;
    
    cin >> n >> q;
    rep(i, 0, n) {
        cin >> p;
        pq.emplace(0, p);
    }

    int val, prime;
    rep(i, 1, 10'000'001) {
        while (1) {
            tie(val, prime) = pq.top();
            val = -val;

            if (i / prime == val / prime) {
                rem = i - val;
                if (!rem)
                    ans[i] = INF;
                else
                    ans[i] = ans[i - rem] + 1;
                break;

            } else {
                pq.pop();
                pq.emplace(-(i - i % prime), prime);
            }
        }
    }

    while (q--) {
        cin >> val;
        if (ans[val] == INF)
            cout << "oo" << endl;
        else
            cout << ans[val] << endl;
    }
    return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 39312 KB Output isn't correct
2 Correct 219 ms 39468 KB Output is correct
3 Correct 231 ms 39304 KB Output is correct
4 Correct 165 ms 39412 KB Output is correct
5 Correct 230 ms 39428 KB Output is correct
6 Incorrect 241 ms 39444 KB Output isn't correct
7 Correct 224 ms 39396 KB Output is correct
8 Correct 239 ms 39396 KB Output is correct
9 Correct 283 ms 39532 KB Output is correct
10 Correct 233 ms 39416 KB Output is correct
11 Correct 236 ms 39340 KB Output is correct
12 Correct 169 ms 39420 KB Output is correct
13 Correct 249 ms 39340 KB Output is correct
14 Correct 250 ms 39420 KB Output is correct
15 Correct 192 ms 39428 KB Output is correct
16 Correct 199 ms 39396 KB Output is correct
17 Correct 220 ms 39452 KB Output is correct
18 Correct 177 ms 39420 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 137 ms 39696 KB Output is correct
2 Correct 126 ms 40248 KB Output is correct
3 Correct 176 ms 40120 KB Output is correct
4 Correct 179 ms 39548 KB Output is correct
5 Correct 174 ms 39964 KB Output is correct
6 Correct 138 ms 39456 KB Output is correct
7 Correct 137 ms 39620 KB Output is correct
8 Correct 168 ms 39408 KB Output is correct
9 Correct 202 ms 40072 KB Output is correct
10 Correct 176 ms 40008 KB Output is correct
11 Correct 233 ms 39800 KB Output is correct
12 Correct 172 ms 39448 KB Output is correct
13 Correct 127 ms 39440 KB Output is correct
14 Correct 162 ms 39380 KB Output is correct
15 Correct 196 ms 39828 KB Output is correct
16 Correct 127 ms 40216 KB Output is correct
17 Correct 211 ms 39472 KB Output is correct
18 Correct 148 ms 40284 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 262 ms 40160 KB Output is correct
2 Correct 271 ms 39992 KB Output is correct
3 Correct 307 ms 40132 KB Output is correct
4 Correct 281 ms 39840 KB Output is correct
5 Correct 291 ms 40508 KB Output is correct
6 Correct 320 ms 39808 KB Output is correct
7 Correct 232 ms 40452 KB Output is correct
8 Correct 256 ms 39972 KB Output is correct
9 Correct 244 ms 40092 KB Output is correct
10 Correct 204 ms 39516 KB Output is correct
11 Correct 202 ms 39600 KB Output is correct
12 Correct 247 ms 39612 KB Output is correct
13 Correct 312 ms 40008 KB Output is correct
14 Correct 424 ms 39972 KB Output is correct
15 Correct 233 ms 39564 KB Output is correct
16 Correct 275 ms 39564 KB Output is correct
17 Correct 234 ms 39876 KB Output is correct
18 Correct 270 ms 40020 KB Output is correct
19 Correct 151 ms 39492 KB Output is correct
20 Correct 292 ms 40012 KB Output is correct
21 Correct 341 ms 39948 KB Output is correct
22 Correct 362 ms 40540 KB Output is correct
23 Correct 289 ms 39952 KB Output is correct
24 Correct 268 ms 39620 KB Output is correct
25 Correct 309 ms 39816 KB Output is correct
26 Correct 287 ms 39752 KB Output is correct
27 Correct 295 ms 40576 KB Output is correct
28 Correct 252 ms 39712 KB Output is correct
29 Correct 362 ms 40464 KB Output is correct
30 Correct 375 ms 40340 KB Output is correct
31 Correct 251 ms 39748 KB Output is correct
32 Correct 282 ms 39684 KB Output is correct
33 Correct 244 ms 39640 KB Output is correct
34 Correct 237 ms 40576 KB Output is correct
35 Correct 265 ms 39668 KB Output is correct
36 Correct 347 ms 40372 KB Output is correct
37 Correct 280 ms 40428 KB Output is correct
38 Correct 314 ms 39748 KB Output is correct
39 Correct 272 ms 39692 KB Output is correct
40 Correct 297 ms 39780 KB Output is correct
41 Correct 212 ms 40364 KB Output is correct
42 Correct 339 ms 39860 KB Output is correct