oj.uz

Submission #1015942

# Submission time Handle Problem Language Result Execution time Memory
1015942 2024-07-07T06:24:43 Z caterpillow Brunhilda’s Birthday (BOI13_brunhilda) C++17
8.09524 / 100
 83 ms 42832 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;
queue<pi> q;

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> m >> qs;
    primes.resize(m);
    F0R (i, m) cin >> primes[i]; 
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    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.front().f + q.front().s == i) {
            q.push({q.front().f + q.front().s, q.front().s});
            q.pop();
        }
        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(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
3.33333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 39516 KB Output isn't correct
2 Incorrect 45 ms 39516 KB Output isn't correct
3 Incorrect 39 ms 39440 KB Output isn't correct
4 Incorrect 50 ms 39900 KB Output isn't correct
5 Incorrect 46 ms 39516 KB Output isn't correct
6 Incorrect 40 ms 39516 KB Output isn't correct
7 Incorrect 40 ms 39512 KB Output isn't correct
8 Incorrect 44 ms 39512 KB Output isn't correct
9 Incorrect 41 ms 39512 KB Output isn't correct
10 Incorrect 53 ms 39424 KB Output isn't correct
11 Incorrect 43 ms 39440 KB Output isn't correct
12 Correct 40 ms 39512 KB Output is correct
13 Correct 41 ms 39516 KB Output is correct
14 Correct 42 ms 39516 KB Output is correct
15 Incorrect 40 ms 39512 KB Output isn't correct
16 Incorrect 40 ms 39512 KB Output isn't correct
17 Incorrect 41 ms 39512 KB Output isn't correct
18 Incorrect 41 ms 39516 KB Output isn't correct

Subtask #2
3.33333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 39516 KB Output isn't correct
2 Correct 51 ms 40728 KB Output is correct
3 Incorrect 55 ms 40284 KB Output isn't correct
4 Incorrect 44 ms 39512 KB Output isn't correct
5 Incorrect 47 ms 40280 KB Output isn't correct
6 Incorrect 41 ms 39516 KB Output isn't correct
7 Incorrect 44 ms 39524 KB Output isn't correct
8 Incorrect 41 ms 39512 KB Output isn't correct
9 Correct 49 ms 40280 KB Output is correct
10 Incorrect 48 ms 40284 KB Output isn't correct
11 Incorrect 47 ms 40016 KB Output isn't correct
12 Incorrect 44 ms 39512 KB Output isn't correct
13 Incorrect 46 ms 39512 KB Output isn't correct
14 Incorrect 46 ms 39516 KB Output isn't correct
15 Incorrect 44 ms 40028 KB Output isn't correct
16 Correct 50 ms 40724 KB Output is correct
17 Incorrect 45 ms 39516 KB Output isn't correct
18 Incorrect 70 ms 40792 KB Output isn't correct

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 40796 KB Output isn't correct
2 Incorrect 58 ms 40572 KB Output isn't correct
3 Incorrect 53 ms 40872 KB Output isn't correct
4 Incorrect 61 ms 41216 KB Output isn't correct
5 Incorrect 68 ms 42832 KB Output isn't correct
6 Incorrect 64 ms 41464 KB Output isn't correct
7 Incorrect 56 ms 41764 KB Output isn't correct
8 Incorrect 60 ms 41040 KB Output isn't correct
9 Incorrect 54 ms 40856 KB Output isn't correct
10 Incorrect 45 ms 39772 KB Output isn't correct
11 Incorrect 47 ms 40016 KB Output isn't correct
12 Incorrect 46 ms 40028 KB Output isn't correct
13 Incorrect 75 ms 41552 KB Output isn't correct
14 Incorrect 54 ms 41468 KB Output isn't correct
15 Incorrect 47 ms 40028 KB Output isn't correct
16 Incorrect 49 ms 39948 KB Output isn't correct
17 Incorrect 50 ms 40280 KB Output isn't correct
18 Incorrect 51 ms 40584 KB Output isn't correct
19 Incorrect 46 ms 39992 KB Output isn't correct
20 Incorrect 51 ms 41044 KB Output isn't correct
21 Incorrect 55 ms 41556 KB Output isn't correct
22 Incorrect 61 ms 42604 KB Output isn't correct
23 Incorrect 72 ms 41736 KB Output isn't correct
24 Incorrect 54 ms 41552 KB Output isn't correct
25 Incorrect 57 ms 41508 KB Output isn't correct
26 Incorrect 52 ms 41296 KB Output isn't correct
27 Incorrect 48 ms 41812 KB Output isn't correct
28 Incorrect 51 ms 41556 KB Output isn't correct
29 Incorrect 59 ms 42592 KB Output isn't correct
30 Incorrect 58 ms 42320 KB Output isn't correct
31 Incorrect 52 ms 41340 KB Output isn't correct
32 Incorrect 54 ms 41304 KB Output isn't correct
33 Incorrect 52 ms 41436 KB Output isn't correct
34 Incorrect 49 ms 41752 KB Output isn't correct
35 Incorrect 49 ms 41560 KB Output isn't correct
36 Incorrect 83 ms 42576 KB Output isn't correct
37 Incorrect 68 ms 42832 KB Output isn't correct
38 Incorrect 56 ms 41548 KB Output isn't correct
39 Incorrect 56 ms 41552 KB Output isn't correct
40 Incorrect 71 ms 41556 KB Output isn't correct
41 Correct 55 ms 41812 KB Output is correct
42 Incorrect 54 ms 41556 KB Output isn't correct