답안 #31862 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31862	2017-09-11T08:01:32 Z	user202729	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	60 / 100	723 ms	80936 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	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

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

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

답안 #31862

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 60.0

Subtask #1
20.0 / 20.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 60.0