oj.uz

Submission #31862

# Submission time Handle Problem Language Result Execution time Memory
31862 2017-09-11T08:01:32 Z user202729 Brunhilda’s Birthday (BOI13_brunhilda) C++14
60 / 100
 723 ms 80936 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 9 ms 41084 KB Output is correct
2 Correct 166 ms 80148 KB Output is correct
3 Correct 6 ms 42120 KB Output is correct
4 Correct 133 ms 80148 KB Output is correct
5 Correct 149 ms 80148 KB Output is correct
6 Correct 9 ms 41084 KB Output is correct
7 Correct 3 ms 42120 KB Output is correct
8 Correct 19 ms 44624 KB Output is correct
9 Correct 159 ms 80148 KB Output is correct
10 Correct 186 ms 80148 KB Output is correct
11 Correct 219 ms 80148 KB Output is correct
12 Correct 86 ms 80148 KB Output is correct
13 Correct 319 ms 80148 KB Output is correct
14 Correct 353 ms 80148 KB Output is correct
15 Correct 163 ms 80148 KB Output is correct
16 Correct 163 ms 80148 KB Output is correct
17 Correct 186 ms 80148 KB Output is correct
18 Correct 116 ms 80148 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 80280 KB Output is correct
2 Correct 226 ms 80904 KB Output is correct
3 Correct 473 ms 80556 KB Output is correct
4 Correct 203 ms 80148 KB Output is correct
5 Correct 366 ms 80616 KB Output is correct
6 Correct 156 ms 80148 KB Output is correct
7 Correct 146 ms 80280 KB Output is correct
8 Correct 196 ms 80148 KB Output is correct
9 Correct 416 ms 80692 KB Output is correct
10 Correct 486 ms 80556 KB Output is correct
11 Correct 456 ms 80440 KB Output is correct
12 Correct 233 ms 80148 KB Output is correct
13 Correct 133 ms 80148 KB Output is correct
14 Correct 216 ms 80148 KB Output is correct
15 Correct 363 ms 80444 KB Output is correct
16 Correct 239 ms 80904 KB Output is correct
17 Correct 389 ms 80148 KB Output is correct
18 Correct 433 ms 80804 KB Output is correct

Subtask #3
20.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 80608 KB Output is correct
2 Correct 536 ms 80620 KB Output is correct
3 Correct 543 ms 80476 KB Output is correct
4 Runtime error 419 ms 80148 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 489 ms 80932 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 536 ms 80280 KB Execution timed out (wall clock limit exceeded)
7 Correct 489 ms 80804 KB Output is correct
8 Correct 489 ms 80608 KB Output is correct
9 Runtime error 593 ms 80608 KB Execution timed out (wall clock limit exceeded)
10 Correct 396 ms 80148 KB Output is correct
11 Correct 439 ms 80148 KB Output is correct
12 Correct 356 ms 80148 KB Output is correct
13 Runtime error 626 ms 80340 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 349 ms 80148 KB Execution timed out (wall clock limit exceeded)
15 Correct 469 ms 80148 KB Output is correct
16 Correct 566 ms 80280 KB Output is correct
17 Correct 506 ms 80456 KB Output is correct
18 Correct 676 ms 80620 KB Output is correct
19 Correct 223 ms 80148 KB Output is correct
20 Runtime error 599 ms 80476 KB Execution timed out (wall clock limit exceeded)
21 Runtime error 426 ms 80148 KB Execution timed out (wall clock limit exceeded)
22 Runtime error 663 ms 80936 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 429 ms 80340 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 313 ms 80148 KB Execution timed out (wall clock limit exceeded)
25 Correct 416 ms 80148 KB Output is correct
26 Runtime error 439 ms 80148 KB Execution timed out (wall clock limit exceeded)
27 Runtime error 716 ms 80804 KB Execution timed out (wall clock limit exceeded)
28 Runtime error 269 ms 80148 KB Execution timed out (wall clock limit exceeded)
29 Runtime error 723 ms 80936 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 609 ms 80688 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 363 ms 80148 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 376 ms 80148 KB Execution timed out (wall clock limit exceeded)
33 Runtime error 286 ms 80148 KB Execution timed out (wall clock limit exceeded)
34 Runtime error 526 ms 80804 KB Execution timed out (wall clock limit exceeded)
35 Runtime error 333 ms 80148 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 623 ms 80896 KB Execution timed out (wall clock limit exceeded)
37 Runtime error 359 ms 80932 KB Execution timed out (wall clock limit exceeded)
38 Runtime error 549 ms 80280 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 366 ms 80148 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 526 ms 80280 KB Execution timed out (wall clock limit exceeded)
41 Runtime error 506 ms 80804 KB Execution timed out (wall clock limit exceeded)
42 Runtime error 533 ms 80148 KB Execution timed out (wall clock limit exceeded)