oj.uz

Submission #1018120

# Submission time Handle Problem Language Result Execution time Memory
1018120 2024-07-09T14:53:52 Z mnbvcxz123 Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 174 ms 155556 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
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;
 
const int maxn = 1e7 + 1;
 
int m, qs; 
int dp[maxn];
vt<int> primes, ans;
vt<pi> queries;
int evs[maxn];
vt<pi> q;
 
main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> m >> qs;
    primes.resize(m);
    F0R (i, m) cin >> primes[i]; 
    sort(all(primes));
    memset(evs, -1, sizeof(evs));
    for (int p : primes) {
        int x = p;
        while (x < maxn) {
            evs[x] = p;
            x += 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);
 
    q.reserve(maxn);
    int front = 0;
    q.pb({0, primes.back()});
 
    FOR (i, 1, maxn) {
        if (evs[i] != -1) q.pb({i, evs[i]});
        while (q[front].f + q[front].s <= i) front++;
 
        if (q[front].f == i) break;
        dp[i] = dp[q[front].f] + 1;
        while (size(queries) && queries.back().f == i) {
            ans[queries.back().s] = dp[i];
            queries.pop_back();
        }
        if (!size(queries)) break;
    }
    F0R (i, qs) {
        if (ans[i] == -1) cout << "oo\n"; 
        else cout << ans[i] << endl;
    }
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39516 KB Output is correct
2 Correct 24 ms 39600 KB Output is correct
3 Correct 24 ms 39516 KB Output is correct
4 Correct 22 ms 39772 KB Output is correct
5 Correct 23 ms 39516 KB Output is correct
6 Correct 21 ms 39516 KB Output is correct
7 Correct 26 ms 39696 KB Output is correct
8 Correct 25 ms 39512 KB Output is correct
9 Correct 31 ms 39512 KB Output is correct
10 Correct 35 ms 39512 KB Output is correct
11 Correct 32 ms 39516 KB Output is correct
12 Correct 17 ms 39516 KB Output is correct
13 Correct 59 ms 39608 KB Output is correct
14 Correct 57 ms 39824 KB Output is correct
15 Correct 27 ms 39516 KB Output is correct
16 Correct 24 ms 39600 KB Output is correct
17 Correct 24 ms 39792 KB Output is correct
18 Correct 19 ms 39772 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 91476 KB Output is correct
2 Correct 95 ms 91508 KB Output is correct
3 Correct 101 ms 93524 KB Output is correct
4 Correct 100 ms 103504 KB Output is correct
5 Correct 67 ms 66788 KB Output is correct
6 Correct 45 ms 69308 KB Output is correct
7 Correct 77 ms 91472 KB Output is correct
8 Correct 55 ms 64852 KB Output is correct
9 Correct 73 ms 68432 KB Output is correct
10 Correct 99 ms 93592 KB Output is correct
11 Correct 171 ms 152476 KB Output is correct
12 Correct 156 ms 123984 KB Output is correct
13 Correct 75 ms 97248 KB Output is correct
14 Correct 98 ms 103504 KB Output is correct
15 Correct 86 ms 75344 KB Output is correct
16 Correct 83 ms 91476 KB Output is correct
17 Correct 134 ms 149204 KB Output is correct
18 Correct 143 ms 147716 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 152144 KB Output is correct
2 Correct 157 ms 152912 KB Output is correct
3 Correct 147 ms 120912 KB Output is correct
4 Correct 138 ms 142672 KB Output is correct
5 Correct 119 ms 100572 KB Output is correct
6 Correct 159 ms 149952 KB Output is correct
7 Correct 121 ms 109112 KB Output is correct
8 Correct 147 ms 152144 KB Output is correct
9 Correct 143 ms 152148 KB Output is correct
10 Correct 137 ms 133216 KB Output is correct
11 Correct 133 ms 125524 KB Output is correct
12 Correct 154 ms 148000 KB Output is correct
13 Correct 125 ms 98132 KB Output is correct
14 Correct 104 ms 107104 KB Output is correct
15 Correct 134 ms 151376 KB Output is correct
16 Correct 148 ms 151852 KB Output is correct
17 Correct 145 ms 143584 KB Output is correct
18 Correct 156 ms 152916 KB Output is correct
19 Correct 94 ms 111956 KB Output is correct
20 Correct 130 ms 120656 KB Output is correct
21 Correct 143 ms 151636 KB Output is correct
22 Correct 167 ms 155556 KB Output is correct
23 Correct 114 ms 102660 KB Output is correct
24 Correct 96 ms 94980 KB Output is correct
25 Correct 146 ms 140288 KB Output is correct
26 Correct 155 ms 142872 KB Output is correct
27 Correct 150 ms 121684 KB Output is correct
28 Correct 97 ms 108368 KB Output is correct
29 Correct 174 ms 149076 KB Output is correct
30 Correct 155 ms 145744 KB Output is correct
31 Correct 119 ms 110348 KB Output is correct
32 Correct 130 ms 117908 KB Output is correct
33 Correct 82 ms 88916 KB Output is correct
34 Correct 115 ms 108884 KB Output is correct
35 Correct 105 ms 109880 KB Output is correct
36 Correct 169 ms 155296 KB Output is correct
37 Correct 116 ms 100432 KB Output is correct
38 Correct 143 ms 149840 KB Output is correct
39 Correct 100 ms 99152 KB Output is correct
40 Correct 137 ms 146516 KB Output is correct
41 Correct 106 ms 113232 KB Output is correct
42 Correct 142 ms 153936 KB Output is correct