oj.uz

Submission #1015947

# Submission time Handle Problem Language Result Execution time Memory
1015947 2024-07-07T06:28:58 Z caterpillow Brunhilda’s Birthday (BOI13_brunhilda) C++17
61.4286 / 100
 1000 ms 43472 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

const int maxn = 1e7 + 1;

int m, qs; 
int dp[maxn];
vt<int> primes, ans;
vt<pi> queries;
priority_queue<pi, vt<pi>, greater<pi>> q;

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> m >> qs;
    primes.resize(m);
    F0R (i, m) cin >> primes[i]; 
    for (int p : primes) q.push({0, p});

    queries.resize(qs);
    F0R (i, qs) cin >> queries[i].f, queries[i].s = i;
    sort(all(queries));
    reverse(all(queries));
    ans.resize(qs, -1);

    FOR (i, 1, maxn) {
        while (q.top().f + q.top().s <= i) {
            q.push({q.top().f + q.top().s, q.top().s});
            q.pop();
        }
        if (q.top().f == i) break;
        dp[i] = dp[q.top().f] + 1;
        while (size(queries) && queries.back().f == i) {
            ans[queries.back().s] = dp[i];
            queries.pop_back();
        }
        if (!size(q)) break;
    }
    F0R (i, qs) {
        if (ans[i] == -1) cout << "oo\n"; 
        else cout << ans[i] << endl;
    }
}

Compilation message

brunhilda.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main() {
      | ^~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 274 ms 39424 KB Output is correct
3 Correct 6 ms 1372 KB Output is correct
4 Correct 61 ms 39508 KB Output is correct
5 Correct 100 ms 39504 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 4 ms 1372 KB Output is correct
8 Correct 19 ms 3780 KB Output is correct
9 Correct 339 ms 39396 KB Output is correct
10 Correct 465 ms 39632 KB Output is correct
11 Correct 351 ms 39380 KB Output is correct
12 Correct 49 ms 39508 KB Output is correct
13 Execution timed out 1097 ms 35740 KB Time limit exceeded
14 Execution timed out 1077 ms 35024 KB Time limit exceeded
15 Correct 306 ms 39508 KB Output is correct
16 Correct 255 ms 39760 KB Output is correct
17 Correct 131 ms 39760 KB Output is correct
18 Correct 80 ms 39688 KB Output is correct

Subtask #2
12.2222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 39728 KB Output is correct
2 Correct 134 ms 41256 KB Output is correct
3 Execution timed out 1098 ms 30792 KB Time limit exceeded
4 Correct 315 ms 39620 KB Output is correct
5 Correct 961 ms 40628 KB Output is correct
6 Correct 314 ms 39604 KB Output is correct
7 Correct 152 ms 39744 KB Output is correct
8 Correct 253 ms 39428 KB Output is correct
9 Execution timed out 1061 ms 36072 KB Time limit exceeded
10 Execution timed out 1034 ms 24452 KB Time limit exceeded
11 Execution timed out 1065 ms 22552 KB Time limit exceeded
12 Correct 706 ms 39548 KB Output is correct
13 Correct 142 ms 39508 KB Output is correct
14 Correct 300 ms 39504 KB Output is correct
15 Execution timed out 1060 ms 30424 KB Time limit exceeded
16 Correct 153 ms 41420 KB Output is correct
17 Execution timed out 1069 ms 28364 KB Time limit exceeded
18 Execution timed out 1069 ms 41180 KB Time limit exceeded

Subtask #3
31.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1049 ms 30264 KB Time limit exceeded
2 Execution timed out 1053 ms 23324 KB Time limit exceeded
3 Execution timed out 1074 ms 22816 KB Time limit exceeded
4 Correct 769 ms 41532 KB Output is correct
5 Correct 236 ms 43472 KB Output is correct
6 Execution timed out 1081 ms 30300 KB Time limit exceeded
7 Correct 817 ms 42444 KB Output is correct
8 Execution timed out 1050 ms 30012 KB Time limit exceeded
9 Execution timed out 1074 ms 29964 KB Time limit exceeded
10 Correct 810 ms 39752 KB Output is correct
11 Correct 564 ms 40020 KB Output is correct
12 Execution timed out 1075 ms 39904 KB Time limit exceeded
13 Execution timed out 1016 ms 27852 KB Time limit exceeded
14 Correct 554 ms 41916 KB Output is correct
15 Execution timed out 1095 ms 33616 KB Time limit exceeded
16 Execution timed out 1054 ms 28380 KB Time limit exceeded
17 Execution timed out 1012 ms 36816 KB Time limit exceeded
18 Execution timed out 1022 ms 25120 KB Time limit exceeded
19 Correct 205 ms 40020 KB Output is correct
20 Execution timed out 1022 ms 25152 KB Time limit exceeded
21 Correct 776 ms 42016 KB Output is correct
22 Execution timed out 1064 ms 29628 KB Time limit exceeded
23 Correct 289 ms 42308 KB Output is correct
24 Correct 145 ms 41532 KB Output is correct
25 Correct 839 ms 41708 KB Output is correct
26 Correct 716 ms 41588 KB Output is correct
27 Execution timed out 1027 ms 23720 KB Time limit exceeded
28 Correct 218 ms 41808 KB Output is correct
29 Execution timed out 1066 ms 37448 KB Time limit exceeded
30 Execution timed out 1061 ms 41416 KB Time limit exceeded
31 Correct 310 ms 41636 KB Output is correct
32 Correct 377 ms 41680 KB Output is correct
33 Correct 107 ms 41556 KB Output is correct
34 Correct 787 ms 42444 KB Output is correct
35 Correct 296 ms 41768 KB Output is correct
36 Execution timed out 1008 ms 28364 KB Time limit exceeded
37 Correct 222 ms 43460 KB Output is correct
38 Execution timed out 1018 ms 34128 KB Time limit exceeded
39 Correct 206 ms 41812 KB Output is correct
40 Correct 987 ms 41812 KB Output is correct
41 Correct 663 ms 42448 KB Output is correct
42 Execution timed out 1072 ms 30604 KB Time limit exceeded