oj.uz

Submission #31855

# Submission time Handle Problem Language Result Execution time Memory
31855 2017-09-11T07:45:18 Z user202729 Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 1000 ms 246040 KB 
//#undef _GLIBCXX_DEBUG
#define NDEBUG

#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
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 17188 KB Output is correct
2 Execution timed out 1000 ms 126548 KB Execution timed out
3 Correct 756 ms 68008 KB Output is correct
4 Correct 186 ms 47456 KB Output is correct
5 Correct 416 ms 65756 KB Output is correct
6 Correct 183 ms 17188 KB Output is correct
7 Correct 753 ms 68008 KB Output is correct
8 Execution timed out 1000 ms 97756 KB Execution timed out
9 Execution timed out 1000 ms 159996 KB Execution timed out
10 Execution timed out 1000 ms 172536 KB Execution timed out
11 Execution timed out 1000 ms 131432 KB Execution timed out
12 Correct 149 ms 45740 KB Output is correct
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 Correct 529 ms 66020 KB Output is correct
18 Correct 223 ms 47456 KB Output is correct

Subtask #2
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 55536 KB Output is correct
2 Correct 493 ms 61004 KB Output is correct
3 Execution timed out 1000 ms 226928 KB Execution timed out
4 Correct 749 ms 81972 KB Output is correct
5 Execution timed out 1000 ms 160524 KB Execution timed out
6 Correct 903 ms 101600 KB Output is correct
7 Correct 326 ms 55536 KB Output is correct
8 Correct 683 ms 77616 KB Output is correct
9 Execution timed out 1000 ms 138620 KB Execution timed out
10 Execution timed out 1000 ms 226928 KB Execution timed out
11 Execution timed out 1000 ms 219140 KB Execution timed out
12 Execution timed out 1000 ms 143312 KB Execution timed out
13 Correct 409 ms 63248 KB Output is correct
14 Correct 753 ms 81972 KB Output is correct
15 Execution timed out 1000 ms 179144 KB Execution timed out
16 Correct 483 ms 61004 KB Output is correct
17 Execution timed out 1000 ms 197756 KB Execution timed out
18 Execution timed out 1000 ms 150500 KB Execution timed out

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 190364 KB Execution timed out
2 Execution timed out 1000 ms 224948 KB Execution timed out
3 Execution timed out 1000 ms 228776 KB Execution timed out
4 Execution timed out 1000 ms 0 KB Execution timed out
5 Runtime error 773 ms 61004 KB Execution timed out (wall clock limit exceeded)
6 Execution timed out 1000 ms 167396 KB Execution timed out
7 Execution timed out 1000 ms 123908 KB Execution timed out
8 Execution timed out 1000 ms 190364 KB Execution timed out
9 Execution timed out 1000 ms 190364 KB Execution timed out
10 Execution timed out 1000 ms 136844 KB Execution timed out
11 Execution timed out 1000 ms 112424 KB Execution timed out
12 Execution timed out 1000 ms 162644 KB Execution timed out
13 Execution timed out 1000 ms 194852 KB Execution timed out
14 Execution timed out 1000 ms 143108 KB Execution timed out
15 Execution timed out 1000 ms 192212 KB Execution timed out
16 Execution timed out 1000 ms 209768 KB Execution timed out
17 Execution timed out 1000 ms 129248 KB Execution timed out
18 Execution timed out 1000 ms 224948 KB Execution timed out
19 Incorrect 703 ms 79992 KB Output isn't correct
20 Execution timed out 1000 ms 228776 KB Execution timed out
21 Execution timed out 1000 ms 165680 KB Execution timed out
22 Execution timed out 1000 ms 217160 KB Execution timed out
23 Runtime error 733 ms 64304 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 533 ms 57704 KB Execution timed out (wall clock limit exceeded)
25 Execution timed out 1000 ms 152024 KB Execution timed out
26 Execution timed out 1000 ms 0 KB Execution timed out
27 Execution timed out 1000 ms 246040 KB Execution timed out
28 Runtime error 753 ms 75240 KB Execution timed out (wall clock limit exceeded)
29 Execution timed out 1000 ms 128456 KB Execution timed out
30 Execution timed out 1000 ms 143312 KB Execution timed out
31 Runtime error 946 ms 79332 KB Execution timed out (wall clock limit exceeded)
32 Execution timed out 1000 ms 91476 KB Execution timed out
33 Runtime error 373 ms 50256 KB Execution timed out (wall clock limit exceeded)
34 Execution timed out 1000 ms 0 KB Execution timed out
35 Runtime error 803 ms 77220 KB Execution timed out (wall clock limit exceeded)
36 Execution timed out 1000 ms 213728 KB Execution timed out
37 Runtime error 666 ms 61004 KB Execution timed out (wall clock limit exceeded)
38 Execution timed out 1000 ms 167396 KB Execution timed out
39 Runtime error 606 ms 62588 KB Execution timed out (wall clock limit exceeded)
40 Execution timed out 1000 ms 136772 KB Execution timed out
41 Execution timed out 1000 ms 145424 KB Execution timed out
42 Execution timed out 1000 ms 210824 KB Execution timed out