oj.uz

Submission #31865

# Submission time Handle Problem Language Result Execution time Memory
31865 2017-09-11T08:04:33 Z user202729 Brunhilda’s Birthday (BOI13_brunhilda) C++14
61.4286 / 100
 793 ms 80932 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;
    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::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() && candidates[0].second <= p) { // expired candidates
            assert(candidates[0].second == p);
            candidates.pop_front();
        }
        if (bestCandidateAt[p] != -1) {
            if (candidates.empty() || bestCandidateAt[p] > candidates.back().second)
                candidates.emplace_back(p, bestCandidateAt[p]);
        }
        assert (!candidates.empty());
        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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41080 KB Output is correct
2 Correct 176 ms 80144 KB Output is correct
3 Correct 9 ms 42116 KB Output is correct
4 Correct 116 ms 80144 KB Output is correct
5 Correct 149 ms 80144 KB Output is correct
6 Correct 16 ms 41080 KB Output is correct
7 Correct 9 ms 42116 KB Output is correct
8 Correct 29 ms 44620 KB Output is correct
9 Correct 159 ms 80144 KB Output is correct
10 Correct 229 ms 80144 KB Output is correct
11 Correct 223 ms 80144 KB Output is correct
12 Correct 76 ms 80144 KB Output is correct
13 Correct 376 ms 80144 KB Output is correct
14 Correct 476 ms 80144 KB Output is correct
15 Correct 173 ms 80144 KB Output is correct
16 Correct 173 ms 80144 KB Output is correct
17 Correct 213 ms 80144 KB Output is correct
18 Correct 119 ms 80144 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 80276 KB Output is correct
2 Correct 199 ms 80900 KB Output is correct
3 Correct 486 ms 80552 KB Output is correct
4 Correct 219 ms 80144 KB Output is correct
5 Correct 333 ms 80612 KB Output is correct
6 Correct 136 ms 80144 KB Output is correct
7 Correct 119 ms 80276 KB Output is correct
8 Correct 186 ms 80144 KB Output is correct
9 Correct 416 ms 80688 KB Output is correct
10 Correct 529 ms 80552 KB Output is correct
11 Correct 413 ms 80436 KB Output is correct
12 Correct 269 ms 80144 KB Output is correct
13 Correct 129 ms 80144 KB Output is correct
14 Correct 216 ms 80144 KB Output is correct
15 Correct 343 ms 80440 KB Output is correct
16 Correct 226 ms 80900 KB Output is correct
17 Correct 296 ms 80144 KB Output is correct
18 Correct 416 ms 80800 KB Output is correct

Subtask #3
21.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 80604 KB Output is correct
2 Runtime error 793 ms 80616 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 636 ms 80472 KB Execution timed out (wall clock limit exceeded)
4 Correct 456 ms 80144 KB Output is correct
5 Runtime error 433 ms 80928 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 593 ms 80276 KB Execution timed out (wall clock limit exceeded)
7 Correct 513 ms 80800 KB Output is correct
8 Correct 406 ms 80604 KB Output is correct
9 Correct 503 ms 80604 KB Output is correct
10 Correct 399 ms 80144 KB Output is correct
11 Correct 383 ms 80144 KB Output is correct
12 Correct 519 ms 80144 KB Output is correct
13 Correct 609 ms 80336 KB Output is correct
14 Runtime error 366 ms 80144 KB Execution timed out (wall clock limit exceeded)
15 Correct 516 ms 80144 KB Output is correct
16 Runtime error 583 ms 80276 KB Execution timed out (wall clock limit exceeded)
17 Correct 449 ms 80452 KB Output is correct
18 Correct 656 ms 80616 KB Output is correct
19 Correct 153 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 743 ms 80932 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 399 ms 80336 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 279 ms 80144 KB Execution timed out (wall clock limit exceeded)
25 Runtime error 543 ms 80144 KB Execution timed out (wall clock limit exceeded)
26 Correct 336 ms 80144 KB Output is correct
27 Runtime error 793 ms 80800 KB Execution timed out (wall clock limit exceeded)
28 Runtime error 346 ms 80144 KB Execution timed out (wall clock limit exceeded)
29 Correct 723 ms 80932 KB Output is correct
30 Runtime error 643 ms 80684 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 423 ms 80144 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 446 ms 80144 KB Execution timed out (wall clock limit exceeded)
33 Runtime error 219 ms 80144 KB Execution timed out (wall clock limit exceeded)
34 Runtime error 579 ms 80800 KB Execution timed out (wall clock limit exceeded)
35 Runtime error 299 ms 80144 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 716 ms 80892 KB Execution timed out (wall clock limit exceeded)
37 Runtime error 443 ms 80928 KB Execution timed out (wall clock limit exceeded)
38 Runtime error 506 ms 80276 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 343 ms 80144 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 493 ms 80276 KB Execution timed out (wall clock limit exceeded)
41 Runtime error 526 ms 80800 KB Execution timed out (wall clock limit exceeded)
42 Runtime error 599 ms 80144 KB Execution timed out (wall clock limit exceeded)