oj.uz

Submission #31873

# Submission time Handle Problem Language Result Execution time Memory
31873 2017-09-11T08:22:46 Z user202729 Brunhilda’s Birthday (BOI13_brunhilda) C++14
64.2857 / 100
 753 ms 80800 KB 
//#undef _GLIBCXX_DEBUG

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

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;
    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)
    std::deque<int> candidates; // store begin positions. end calculated by bestCandidateAt
    std::vector<int> primes (m);
    for (int& p_i : primes) {
        std::cin >> p_i;
        lcm_all = lcm(lcm_all, p_i); // lcm will return inf if result > inf
    }
//    // should be unnecessary
//    std::sort(primes.begin(), primes.end());
//    primes.erase(std::unique(primes.begin(), primes.end()), primes.end());

    maxN = std::min(maxN, lcm_all);
    std::vector<int> bestCandidateAt (maxN, -1);

    for (int p_i : primes) {
        for (int multiple_of_p_i = 0; multiple_of_p_i < maxN; multiple_of_p_i += p_i) {
            bestCandidateAt[multiple_of_p_i] = multiple_of_p_i + p_i; // after the loop the furthest one will be recorded
        }
    }
//    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;
//    });
    std::vector<int> f (maxN);
    for (int p = 0; p < maxN; ++p) {
        while (!candidates.empty() && bestCandidateAt[candidates.front()] <= p) { // expired candidates
            candidates.pop_front();
        }
        if (bestCandidateAt[p] != -1) {
            if (candidates.empty() || bestCandidateAt[p] > bestCandidateAt[candidates.back()])
                candidates.push_back(p);
        }
        f[p] = p == 0 ? 0 : (1+f[candidates.front()]);
    }

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2016 KB Output is correct
2 Correct 133 ms 80144 KB Output is correct
3 Correct 0 ms 4088 KB Output is correct
4 Correct 83 ms 80144 KB Output is correct
5 Correct 129 ms 80144 KB Output is correct
6 Correct 16 ms 2016 KB Output is correct
7 Correct 3 ms 4088 KB Output is correct
8 Correct 16 ms 9096 KB Output is correct
9 Correct 189 ms 80144 KB Output is correct
10 Correct 199 ms 80144 KB Output is correct
11 Correct 196 ms 80144 KB Output is correct
12 Correct 76 ms 80144 KB Output is correct
13 Correct 333 ms 80144 KB Output is correct
14 Correct 333 ms 80144 KB Output is correct
15 Correct 136 ms 80144 KB Output is correct
16 Correct 119 ms 80144 KB Output is correct
17 Correct 139 ms 80144 KB Output is correct
18 Correct 126 ms 80144 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 80276 KB Output is correct
2 Correct 193 ms 80636 KB Output is correct
3 Correct 449 ms 80552 KB Output is correct
4 Correct 199 ms 80144 KB Output is correct
5 Correct 336 ms 80480 KB Output is correct
6 Correct 116 ms 80144 KB Output is correct
7 Correct 116 ms 80276 KB Output is correct
8 Correct 169 ms 80144 KB Output is correct
9 Correct 409 ms 80556 KB Output is correct
10 Correct 469 ms 80552 KB Output is correct
11 Correct 453 ms 80304 KB Output is correct
12 Correct 229 ms 80144 KB Output is correct
13 Correct 96 ms 80144 KB Output is correct
14 Correct 186 ms 80144 KB Output is correct
15 Correct 359 ms 80440 KB Output is correct
16 Correct 219 ms 80636 KB Output is correct
17 Correct 339 ms 80144 KB Output is correct
18 Correct 429 ms 80668 KB Output is correct

Subtask #3
24.2857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 626 ms 80472 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 676 ms 80484 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 613 ms 80472 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 409 ms 80144 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 413 ms 80796 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 489 ms 80144 KB Execution timed out (wall clock limit exceeded)
7 Correct 509 ms 80668 KB Output is correct
8 Correct 456 ms 80472 KB Output is correct
9 Correct 496 ms 80472 KB Output is correct
10 Correct 363 ms 80144 KB Output is correct
11 Correct 353 ms 80144 KB Output is correct
12 Correct 426 ms 80144 KB Output is correct
13 Runtime error 666 ms 80336 KB Execution timed out (wall clock limit exceeded)
14 Correct 373 ms 80144 KB Output is correct
15 Correct 366 ms 80144 KB Output is correct
16 Correct 579 ms 80144 KB Output is correct
17 Correct 476 ms 80452 KB Output is correct
18 Correct 599 ms 80484 KB Output is correct
19 Correct 203 ms 80144 KB Output is correct
20 Runtime error 616 ms 80472 KB Execution timed out (wall clock limit exceeded)
21 Runtime error 376 ms 80144 KB Execution timed out (wall clock limit exceeded)
22 Runtime error 613 ms 80800 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 333 ms 80336 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 256 ms 80144 KB Execution timed out (wall clock limit exceeded)
25 Correct 533 ms 80144 KB Output is correct
26 Correct 403 ms 80144 KB Output is correct
27 Correct 753 ms 80668 KB Output is correct
28 Runtime error 256 ms 80144 KB Execution timed out (wall clock limit exceeded)
29 Runtime error 656 ms 80800 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 626 ms 80552 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 313 ms 80144 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 396 ms 80144 KB Execution timed out (wall clock limit exceeded)
33 Runtime error 239 ms 80144 KB Execution timed out (wall clock limit exceeded)
34 Runtime error 556 ms 80668 KB Execution timed out (wall clock limit exceeded)
35 Runtime error 273 ms 80144 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 703 ms 80628 KB Execution timed out (wall clock limit exceeded)
37 Correct 396 ms 80796 KB Output is correct
38 Runtime error 516 ms 80144 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 289 ms 80144 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 473 ms 80276 KB Execution timed out (wall clock limit exceeded)
41 Correct 509 ms 80668 KB Output is correct
42 Runtime error 536 ms 80144 KB Execution timed out (wall clock limit exceeded)