답안 #31865 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31865	2017-09-11T08:04:33 Z	user202729	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	61.4286 / 100	793 ms	80932 KB

brunhilda

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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)

답안 #31865

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 20.0 / 20.0

Subtask #3 21.4285714286 / 60.0

Subtask #1
20.0 / 20.0

Subtask #2
20.0 / 20.0

Subtask #3
21.4285714286 / 60.0