답안 #31873 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31873	2017-09-11T08:22:46 Z	user202729	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	64.2857 / 100	753 ms	80800 KB

brunhilda

//#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());

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

    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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2016 KB	Output is correct
2	Correct	133 ms	80144 KB	Output is correct
3	Correct	0 ms	4088 KB	Output is correct
4	Correct	83 ms	80144 KB	Output is correct
5	Correct	129 ms	80144 KB	Output is correct
6	Correct	16 ms	2016 KB	Output is correct
7	Correct	3 ms	4088 KB	Output is correct
8	Correct	16 ms	9096 KB	Output is correct
9	Correct	189 ms	80144 KB	Output is correct
10	Correct	199 ms	80144 KB	Output is correct
11	Correct	196 ms	80144 KB	Output is correct
12	Correct	76 ms	80144 KB	Output is correct
13	Correct	333 ms	80144 KB	Output is correct
14	Correct	333 ms	80144 KB	Output is correct
15	Correct	136 ms	80144 KB	Output is correct
16	Correct	119 ms	80144 KB	Output is correct
17	Correct	139 ms	80144 KB	Output is correct
18	Correct	126 ms	80144 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	123 ms	80276 KB	Output is correct
2	Correct	193 ms	80636 KB	Output is correct
3	Correct	449 ms	80552 KB	Output is correct
4	Correct	199 ms	80144 KB	Output is correct
5	Correct	336 ms	80480 KB	Output is correct
6	Correct	116 ms	80144 KB	Output is correct
7	Correct	116 ms	80276 KB	Output is correct
8	Correct	169 ms	80144 KB	Output is correct
9	Correct	409 ms	80556 KB	Output is correct
10	Correct	469 ms	80552 KB	Output is correct
11	Correct	453 ms	80304 KB	Output is correct
12	Correct	229 ms	80144 KB	Output is correct
13	Correct	96 ms	80144 KB	Output is correct
14	Correct	186 ms	80144 KB	Output is correct
15	Correct	359 ms	80440 KB	Output is correct
16	Correct	219 ms	80636 KB	Output is correct
17	Correct	339 ms	80144 KB	Output is correct
18	Correct	429 ms	80668 KB	Output is correct

Subtask #3
24.2857142857 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	626 ms	80472 KB	Execution timed out (wall clock limit exceeded)
2	Runtime error	676 ms	80484 KB	Execution timed out (wall clock limit exceeded)
3	Runtime error	613 ms	80472 KB	Execution timed out (wall clock limit exceeded)
4	Runtime error	409 ms	80144 KB	Execution timed out (wall clock limit exceeded)
5	Runtime error	413 ms	80796 KB	Execution timed out (wall clock limit exceeded)
6	Runtime error	489 ms	80144 KB	Execution timed out (wall clock limit exceeded)
7	Correct	509 ms	80668 KB	Output is correct
8	Correct	456 ms	80472 KB	Output is correct
9	Correct	496 ms	80472 KB	Output is correct
10	Correct	363 ms	80144 KB	Output is correct
11	Correct	353 ms	80144 KB	Output is correct
12	Correct	426 ms	80144 KB	Output is correct
13	Runtime error	666 ms	80336 KB	Execution timed out (wall clock limit exceeded)
14	Correct	373 ms	80144 KB	Output is correct
15	Correct	366 ms	80144 KB	Output is correct
16	Correct	579 ms	80144 KB	Output is correct
17	Correct	476 ms	80452 KB	Output is correct
18	Correct	599 ms	80484 KB	Output is correct
19	Correct	203 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	613 ms	80800 KB	Execution timed out (wall clock limit exceeded)
23	Runtime error	333 ms	80336 KB	Execution timed out (wall clock limit exceeded)
24	Runtime error	256 ms	80144 KB	Execution timed out (wall clock limit exceeded)
25	Correct	533 ms	80144 KB	Output is correct
26	Correct	403 ms	80144 KB	Output is correct
27	Correct	753 ms	80668 KB	Output is correct
28	Runtime error	256 ms	80144 KB	Execution timed out (wall clock limit exceeded)
29	Runtime error	656 ms	80800 KB	Execution timed out (wall clock limit exceeded)
30	Runtime error	626 ms	80552 KB	Execution timed out (wall clock limit exceeded)
31	Runtime error	313 ms	80144 KB	Execution timed out (wall clock limit exceeded)
32	Runtime error	396 ms	80144 KB	Execution timed out (wall clock limit exceeded)
33	Runtime error	239 ms	80144 KB	Execution timed out (wall clock limit exceeded)
34	Runtime error	556 ms	80668 KB	Execution timed out (wall clock limit exceeded)
35	Runtime error	273 ms	80144 KB	Execution timed out (wall clock limit exceeded)
36	Runtime error	703 ms	80628 KB	Execution timed out (wall clock limit exceeded)
37	Correct	396 ms	80796 KB	Output is correct
38	Runtime error	516 ms	80144 KB	Execution timed out (wall clock limit exceeded)
39	Runtime error	289 ms	80144 KB	Execution timed out (wall clock limit exceeded)
40	Runtime error	473 ms	80276 KB	Execution timed out (wall clock limit exceeded)
41	Correct	509 ms	80668 KB	Output is correct
42	Runtime error	536 ms	80144 KB	Execution timed out (wall clock limit exceeded)

답안 #31873

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 20.0 / 20.0

Subtask #3 24.2857142857 / 60.0

Subtask #1
20.0 / 20.0

Subtask #2
20.0 / 20.0

Subtask #3
24.2857142857 / 60.0