답안 #31871 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31871	2017-09-11T08:20:06 Z	user202729	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	67.1429 / 100	759 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());

    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() && 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	41080 KB	Output is correct
2	Correct	129 ms	80144 KB	Output is correct
3	Correct	13 ms	42116 KB	Output is correct
4	Correct	83 ms	80144 KB	Output is correct
5	Correct	136 ms	80144 KB	Output is correct
6	Correct	13 ms	41080 KB	Output is correct
7	Correct	13 ms	42116 KB	Output is correct
8	Correct	19 ms	44620 KB	Output is correct
9	Correct	176 ms	80144 KB	Output is correct
10	Correct	176 ms	80144 KB	Output is correct
11	Correct	193 ms	80144 KB	Output is correct
12	Correct	73 ms	80144 KB	Output is correct
13	Correct	356 ms	80144 KB	Output is correct
14	Correct	343 ms	80144 KB	Output is correct
15	Correct	153 ms	80144 KB	Output is correct
16	Correct	119 ms	80144 KB	Output is correct
17	Correct	189 ms	80144 KB	Output is correct
18	Correct	93 ms	80144 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	126 ms	80276 KB	Output is correct
2	Correct	209 ms	80636 KB	Output is correct
3	Correct	466 ms	80552 KB	Output is correct
4	Correct	186 ms	80144 KB	Output is correct
5	Correct	316 ms	80480 KB	Output is correct
6	Correct	109 ms	80144 KB	Output is correct
7	Correct	116 ms	80276 KB	Output is correct
8	Correct	163 ms	80144 KB	Output is correct
9	Correct	393 ms	80556 KB	Output is correct
10	Correct	449 ms	80552 KB	Output is correct
11	Correct	386 ms	80304 KB	Output is correct
12	Correct	216 ms	80144 KB	Output is correct
13	Correct	96 ms	80144 KB	Output is correct
14	Correct	193 ms	80144 KB	Output is correct
15	Correct	363 ms	80440 KB	Output is correct
16	Correct	203 ms	80636 KB	Output is correct
17	Correct	319 ms	80144 KB	Output is correct
18	Correct	413 ms	80668 KB	Output is correct

Subtask #3
27.1428571429 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	456 ms	80472 KB	Output is correct
2	Correct	619 ms	80484 KB	Output is correct
3	Runtime error	646 ms	80472 KB	Execution timed out (wall clock limit exceeded)
4	Runtime error	403 ms	80144 KB	Execution timed out (wall clock limit exceeded)
5	Runtime error	409 ms	80796 KB	Execution timed out (wall clock limit exceeded)
6	Runtime error	543 ms	80144 KB	Execution timed out (wall clock limit exceeded)
7	Correct	506 ms	80668 KB	Output is correct
8	Correct	423 ms	80472 KB	Output is correct
9	Runtime error	519 ms	80472 KB	Execution timed out (wall clock limit exceeded)
10	Correct	389 ms	80144 KB	Output is correct
11	Correct	323 ms	80144 KB	Output is correct
12	Correct	463 ms	80144 KB	Output is correct
13	Runtime error	589 ms	80336 KB	Execution timed out (wall clock limit exceeded)
14	Runtime error	279 ms	80144 KB	Execution timed out (wall clock limit exceeded)
15	Correct	379 ms	80144 KB	Output is correct
16	Correct	419 ms	80144 KB	Output is correct
17	Correct	469 ms	80452 KB	Output is correct
18	Correct	496 ms	80484 KB	Output is correct
19	Correct	136 ms	80144 KB	Output is correct
20	Correct	539 ms	80472 KB	Output is correct
21	Runtime error	399 ms	80144 KB	Execution timed out (wall clock limit exceeded)
22	Runtime error	759 ms	80800 KB	Execution timed out (wall clock limit exceeded)
23	Runtime error	319 ms	80336 KB	Execution timed out (wall clock limit exceeded)
24	Correct	243 ms	80144 KB	Output is correct
25	Runtime error	436 ms	80144 KB	Execution timed out (wall clock limit exceeded)
26	Runtime error	389 ms	80144 KB	Execution timed out (wall clock limit exceeded)
27	Correct	573 ms	80668 KB	Output is correct
28	Runtime error	253 ms	80144 KB	Execution timed out (wall clock limit exceeded)
29	Runtime error	673 ms	80800 KB	Execution timed out (wall clock limit exceeded)
30	Runtime error	613 ms	80552 KB	Execution timed out (wall clock limit exceeded)
31	Runtime error	359 ms	80144 KB	Execution timed out (wall clock limit exceeded)
32	Runtime error	379 ms	80144 KB	Execution timed out (wall clock limit exceeded)
33	Runtime error	246 ms	80144 KB	Execution timed out (wall clock limit exceeded)
34	Correct	603 ms	80668 KB	Output is correct
35	Runtime error	313 ms	80144 KB	Execution timed out (wall clock limit exceeded)
36	Runtime error	626 ms	80628 KB	Execution timed out (wall clock limit exceeded)
37	Runtime error	426 ms	80796 KB	Execution timed out (wall clock limit exceeded)
38	Runtime error	523 ms	80144 KB	Execution timed out (wall clock limit exceeded)
39	Runtime error	299 ms	80144 KB	Execution timed out (wall clock limit exceeded)
40	Correct	406 ms	80276 KB	Output is correct
41	Correct	499 ms	80668 KB	Output is correct
42	Correct	573 ms	80144 KB	Output is correct

답안 #31871

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 20.0 / 20.0

Subtask #3 27.1428571429 / 60.0

Subtask #1
20.0 / 20.0

Subtask #2
20.0 / 20.0

Subtask #3
27.1428571429 / 60.0