oj.uz

Submission #31852

# Submission time Handle Problem Language Result Execution time Memory
31852 2017-09-11T07:43:48 Z user202729 Brunhilda’s Birthday (BOI13_brunhilda) C++14
2.22222 / 100
 1000 ms 226268 KB 
#undef _GLIBCXX_DEBUG

#include <iostream>
#include <vector>
#include <array>
#include <limits>
#include <algorithm>
#include <deque>
#include <cassert>

int maxN = 10'000'005;
//std::array<bool, maxN> mark;
//{ lcm
typedef int64_t ll;
const ll inf = std::numeric_limits<int>::max();
int lcm(int x, int _y) {
    //}
    ll y = _y;
    return (int)std::min(inf, y / std::__gcd((ll)x, y) * x);
}

typedef std::pair<int,int> candidate; // [start, end)

int main() {
    int m, q;
    std::cin >> m >> q;
//    std::vector<int> primes(m);
    int lcm_all = 1;
    std::deque<candidate> segments; // also need to be deque
    std::deque<candidate> candidates; // candidates is sorted in increasing begin (thus increasing end)
    while (m --> 0) {
        int p_i; std::cin >> p_i;
        std::cerr << "p_i = " << p_i << '\n';
        lcm_all = lcm(lcm_all, p_i); // lcm will return inf if result > inf
        for (int multiple_of_p_i = p_i; multiple_of_p_i < maxN; multiple_of_p_i += p_i) {
            segments.emplace_back(multiple_of_p_i - p_i, multiple_of_p_i);
        }
    }
    std::cerr << "begin sorting. Number of elements = " << segments.end() - segments.begin() << "\n";
    std::sort(segments.begin(), segments.end(), [](candidate x, candidate y){
        if (x.first != y.first) return x.first < y.first;
        return x.second > y.second;
    });
    maxN = std::min(maxN, lcm_all);
    std::cerr << "maxN = " << maxN << '\n';
    std::vector<int> f (maxN);
    for (int p = 0; p < maxN; ++p) {
        while (!candidates.empty() && candidates[0].second <= p) { // expired candidates
            assert(candidates[0].second == p);
            candidates.pop_front();
        }
        while (!segments.empty() && segments[0].first <= p) {
            assert(segments[0].first == p);
            if (candidates.empty() || segments[0].second > candidates.back().second)
                candidates.push_back(segments[0]);
            segments.pop_front();
        }
        assert (!candidates.empty());
        std::cerr << p << " get from " << candidates[0].first << '\n';
        f[p] = p == 0 ? 0 : (1+f[candidates[0].first]);
    }

    while (q --> 0) {
        int val; std::cin >> val;
        if (val >= lcm_all) std::cout << "oo\n";
        else std::cout << f.at(val) << '\n';
    }
}

Subtask #1
2.22222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 17188 KB Output is correct
2 Execution timed out 1000 ms 126548 KB Execution timed out
3 Runtime error 816 ms 68008 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 119 ms 47456 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 393 ms 65756 KB Execution timed out (wall clock limit exceeded)
6 Correct 243 ms 17188 KB Output is correct
7 Runtime error 779 ms 68008 KB Execution timed out (wall clock limit exceeded)
8 Execution timed out 1000 ms 97756 KB Execution timed out
9 Execution timed out 1000 ms 0 KB Execution timed out
10 Execution timed out 1000 ms 0 KB Execution timed out
11 Execution timed out 1000 ms 131432 KB Execution timed out
12 Runtime error 136 ms 45740 KB Execution timed out (wall clock limit exceeded)
13 Execution timed out 1000 ms 199472 KB Execution timed out
14 Execution timed out 1000 ms 199340 KB Execution timed out
15 Execution timed out 1000 ms 124172 KB Execution timed out
16 Execution timed out 1000 ms 126548 KB Execution timed out
17 Runtime error 469 ms 66020 KB Execution timed out (wall clock limit exceeded)
18 Runtime error 109 ms 47456 KB Execution timed out (wall clock limit exceeded)

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 306 ms 55536 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 83 ms 20356 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 193 ms 217292 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 679 ms 81972 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 133 ms 112828 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 863 ms 101600 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 319 ms 55536 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 686 ms 77616 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 153 ms 129776 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 183 ms 218612 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 199 ms 212540 KB Execution timed out (wall clock limit exceeded)
12 Execution timed out 1000 ms 143312 KB Execution timed out
13 Runtime error 349 ms 63248 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 686 ms 81972 KB Execution timed out (wall clock limit exceeded)
15 Runtime error 196 ms 175184 KB Execution timed out (wall clock limit exceeded)
16 Runtime error 63 ms 20092 KB Execution timed out (wall clock limit exceeded)
17 Runtime error 249 ms 197756 KB Execution timed out (wall clock limit exceeded)
18 Runtime error 176 ms 140996 KB Execution timed out (wall clock limit exceeded)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 349 ms 182048 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 283 ms 213332 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 219 ms 217160 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 93 ms 114544 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 73 ms 17980 KB Execution timed out (wall clock limit exceeded)
6 Execution timed out 1000 ms 167396 KB Execution timed out
7 Runtime error 153 ms 79696 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 153 ms 183236 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 183 ms 184160 KB Execution timed out (wall clock limit exceeded)
10 Execution timed out 1000 ms 136844 KB Execution timed out
11 Execution timed out 1000 ms 112424 KB Execution timed out
12 Runtime error 106 ms 162644 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 136 ms 191552 KB Execution timed out (wall clock limit exceeded)
14 Execution timed out 1000 ms 143108 KB Execution timed out
15 Runtime error 183 ms 192212 KB Execution timed out (wall clock limit exceeded)
16 Runtime error 126 ms 209768 KB Execution timed out (wall clock limit exceeded)
17 Runtime error 166 ms 124100 KB Execution timed out (wall clock limit exceeded)
18 Runtime error 179 ms 218216 KB Execution timed out (wall clock limit exceeded)
19 Runtime error 596 ms 79992 KB Execution timed out (wall clock limit exceeded)
20 Runtime error 166 ms 218612 KB Execution timed out (wall clock limit exceeded)
21 Execution timed out 1000 ms 165680 KB Execution timed out
22 Runtime error 179 ms 207524 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 109 ms 23524 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 329 ms 57704 KB Execution timed out (wall clock limit exceeded)
25 Execution timed out 1000 ms 0 KB Execution timed out
26 Execution timed out 1000 ms 0 KB Execution timed out
27 Runtime error 216 ms 226268 KB Execution timed out (wall clock limit exceeded)
28 Runtime error 513 ms 75240 KB Execution timed out (wall clock limit exceeded)
29 Runtime error 133 ms 122308 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 126 ms 95668 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 673 ms 79332 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 773 ms 91476 KB Execution timed out (wall clock limit exceeded)
33 Runtime error 183 ms 50256 KB Execution timed out (wall clock limit exceeded)
34 Runtime error 123 ms 76924 KB Execution timed out (wall clock limit exceeded)
35 Runtime error 643 ms 77220 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 149 ms 203696 KB Execution timed out (wall clock limit exceeded)
37 Runtime error 126 ms 19300 KB Execution timed out (wall clock limit exceeded)
38 Runtime error 166 ms 167396 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 389 ms 62588 KB Execution timed out (wall clock limit exceeded)
40 Execution timed out 1000 ms 136772 KB Execution timed out
41 Runtime error 99 ms 100552 KB Execution timed out (wall clock limit exceeded)
42 Execution timed out 1000 ms 210824 KB Execution timed out