oj.uz

Submission #31871

# Submission time Handle Problem Language Result Execution time Memory
31871 2017-09-11T08:20:06 Z user202729 Brunhilda’s Birthday (BOI13_brunhilda) C++14
67.1429 / 100
 759 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());

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

    maxN = std::min(maxN, lcm_all);
    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 41080 KB Output is correct
2 Correct 129 ms 80144 KB Output is correct
3 Correct 13 ms 42116 KB Output is correct
4 Correct 83 ms 80144 KB Output is correct
5 Correct 136 ms 80144 KB Output is correct
6 Correct 13 ms 41080 KB Output is correct
7 Correct 13 ms 42116 KB Output is correct
8 Correct 19 ms 44620 KB Output is correct
9 Correct 176 ms 80144 KB Output is correct
10 Correct 176 ms 80144 KB Output is correct
11 Correct 193 ms 80144 KB Output is correct
12 Correct 73 ms 80144 KB Output is correct
13 Correct 356 ms 80144 KB Output is correct
14 Correct 343 ms 80144 KB Output is correct
15 Correct 153 ms 80144 KB Output is correct
16 Correct 119 ms 80144 KB Output is correct
17 Correct 189 ms 80144 KB Output is correct
18 Correct 93 ms 80144 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 80276 KB Output is correct
2 Correct 209 ms 80636 KB Output is correct
3 Correct 466 ms 80552 KB Output is correct
4 Correct 186 ms 80144 KB Output is correct
5 Correct 316 ms 80480 KB Output is correct
6 Correct 109 ms 80144 KB Output is correct
7 Correct 116 ms 80276 KB Output is correct
8 Correct 163 ms 80144 KB Output is correct
9 Correct 393 ms 80556 KB Output is correct
10 Correct 449 ms 80552 KB Output is correct
11 Correct 386 ms 80304 KB Output is correct
12 Correct 216 ms 80144 KB Output is correct
13 Correct 96 ms 80144 KB Output is correct
14 Correct 193 ms 80144 KB Output is correct
15 Correct 363 ms 80440 KB Output is correct
16 Correct 203 ms 80636 KB Output is correct
17 Correct 319 ms 80144 KB Output is correct
18 Correct 413 ms 80668 KB Output is correct

Subtask #3
27.1428571429 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 80472 KB Output is correct
2 Correct 619 ms 80484 KB Output is correct
3 Runtime error 646 ms 80472 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 403 ms 80144 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 409 ms 80796 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 543 ms 80144 KB Execution timed out (wall clock limit exceeded)
7 Correct 506 ms 80668 KB Output is correct
8 Correct 423 ms 80472 KB Output is correct
9 Runtime error 519 ms 80472 KB Execution timed out (wall clock limit exceeded)
10 Correct 389 ms 80144 KB Output is correct
11 Correct 323 ms 80144 KB Output is correct
12 Correct 463 ms 80144 KB Output is correct
13 Runtime error 589 ms 80336 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 279 ms 80144 KB Execution timed out (wall clock limit exceeded)
15 Correct 379 ms 80144 KB Output is correct
16 Correct 419 ms 80144 KB Output is correct
17 Correct 469 ms 80452 KB Output is correct
18 Correct 496 ms 80484 KB Output is correct
19 Correct 136 ms 80144 KB Output is correct
20 Correct 539 ms 80472 KB Output is correct
21 Runtime error 399 ms 80144 KB Execution timed out (wall clock limit exceeded)
22 Runtime error 759 ms 80800 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 319 ms 80336 KB Execution timed out (wall clock limit exceeded)
24 Correct 243 ms 80144 KB Output is correct
25 Runtime error 436 ms 80144 KB Execution timed out (wall clock limit exceeded)
26 Runtime error 389 ms 80144 KB Execution timed out (wall clock limit exceeded)
27 Correct 573 ms 80668 KB Output is correct
28 Runtime error 253 ms 80144 KB Execution timed out (wall clock limit exceeded)
29 Runtime error 673 ms 80800 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 613 ms 80552 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 359 ms 80144 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 379 ms 80144 KB Execution timed out (wall clock limit exceeded)
33 Runtime error 246 ms 80144 KB Execution timed out (wall clock limit exceeded)
34 Correct 603 ms 80668 KB Output is correct
35 Runtime error 313 ms 80144 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 626 ms 80628 KB Execution timed out (wall clock limit exceeded)
37 Runtime error 426 ms 80796 KB Execution timed out (wall clock limit exceeded)
38 Runtime error 523 ms 80144 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 299 ms 80144 KB Execution timed out (wall clock limit exceeded)
40 Correct 406 ms 80276 KB Output is correct
41 Correct 499 ms 80668 KB Output is correct
42 Correct 573 ms 80144 KB Output is correct