답안 #31855 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31855	2017-09-11T07:45:18 Z	user202729	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	20 / 100	1000 ms	246040 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;
//    std::vector<int> primes(m);
    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)
    while (m --> 0) {
        int p_i; std::cin >> p_i;
//        std::cerr << "p_i = " << p_i << '\n';
        lcm_all = lcm(lcm_all, p_i); // lcm will return inf if result > inf
        for (int multiple_of_p_i = p_i; multiple_of_p_i < maxN; multiple_of_p_i += p_i) {
            segments.emplace_back(multiple_of_p_i - p_i, multiple_of_p_i);
        }
    }
//    std::cerr << "begin sorting. Number of elements = " << segments.end() - segments.begin() << "\n";
    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;
    });
    maxN = std::min(maxN, lcm_all);
//    std::cerr << "maxN = " << maxN << '\n';
    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();
        }
        while (!segments.empty() && segments[0].first <= p) {
            assert(segments[0].first == p);
            if (candidates.empty() || segments[0].second > candidates.back().second)
                candidates.push_back(segments[0]);
            segments.pop_front();
        }
        assert (!candidates.empty());
//        std::cerr << p << " get from " << candidates[0].first << '\n';
        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
10.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	159 ms	17188 KB	Output is correct
2	Execution timed out	1000 ms	126548 KB	Execution timed out
3	Correct	756 ms	68008 KB	Output is correct
4	Correct	186 ms	47456 KB	Output is correct
5	Correct	416 ms	65756 KB	Output is correct
6	Correct	183 ms	17188 KB	Output is correct
7	Correct	753 ms	68008 KB	Output is correct
8	Execution timed out	1000 ms	97756 KB	Execution timed out
9	Execution timed out	1000 ms	159996 KB	Execution timed out
10	Execution timed out	1000 ms	172536 KB	Execution timed out
11	Execution timed out	1000 ms	131432 KB	Execution timed out
12	Correct	149 ms	45740 KB	Output is correct
13	Execution timed out	1000 ms	199472 KB	Execution timed out
14	Execution timed out	1000 ms	199340 KB	Execution timed out
15	Execution timed out	1000 ms	124172 KB	Execution timed out
16	Execution timed out	1000 ms	126548 KB	Execution timed out
17	Correct	529 ms	66020 KB	Output is correct
18	Correct	223 ms	47456 KB	Output is correct

Subtask #2
10.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	326 ms	55536 KB	Output is correct
2	Correct	493 ms	61004 KB	Output is correct
3	Execution timed out	1000 ms	226928 KB	Execution timed out
4	Correct	749 ms	81972 KB	Output is correct
5	Execution timed out	1000 ms	160524 KB	Execution timed out
6	Correct	903 ms	101600 KB	Output is correct
7	Correct	326 ms	55536 KB	Output is correct
8	Correct	683 ms	77616 KB	Output is correct
9	Execution timed out	1000 ms	138620 KB	Execution timed out
10	Execution timed out	1000 ms	226928 KB	Execution timed out
11	Execution timed out	1000 ms	219140 KB	Execution timed out
12	Execution timed out	1000 ms	143312 KB	Execution timed out
13	Correct	409 ms	63248 KB	Output is correct
14	Correct	753 ms	81972 KB	Output is correct
15	Execution timed out	1000 ms	179144 KB	Execution timed out
16	Correct	483 ms	61004 KB	Output is correct
17	Execution timed out	1000 ms	197756 KB	Execution timed out
18	Execution timed out	1000 ms	150500 KB	Execution timed out

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1000 ms	190364 KB	Execution timed out
2	Execution timed out	1000 ms	224948 KB	Execution timed out
3	Execution timed out	1000 ms	228776 KB	Execution timed out
4	Execution timed out	1000 ms	0 KB	Execution timed out
5	Runtime error	773 ms	61004 KB	Execution timed out (wall clock limit exceeded)
6	Execution timed out	1000 ms	167396 KB	Execution timed out
7	Execution timed out	1000 ms	123908 KB	Execution timed out
8	Execution timed out	1000 ms	190364 KB	Execution timed out
9	Execution timed out	1000 ms	190364 KB	Execution timed out
10	Execution timed out	1000 ms	136844 KB	Execution timed out
11	Execution timed out	1000 ms	112424 KB	Execution timed out
12	Execution timed out	1000 ms	162644 KB	Execution timed out
13	Execution timed out	1000 ms	194852 KB	Execution timed out
14	Execution timed out	1000 ms	143108 KB	Execution timed out
15	Execution timed out	1000 ms	192212 KB	Execution timed out
16	Execution timed out	1000 ms	209768 KB	Execution timed out
17	Execution timed out	1000 ms	129248 KB	Execution timed out
18	Execution timed out	1000 ms	224948 KB	Execution timed out
19	Incorrect	703 ms	79992 KB	Output isn't correct
20	Execution timed out	1000 ms	228776 KB	Execution timed out
21	Execution timed out	1000 ms	165680 KB	Execution timed out
22	Execution timed out	1000 ms	217160 KB	Execution timed out
23	Runtime error	733 ms	64304 KB	Execution timed out (wall clock limit exceeded)
24	Runtime error	533 ms	57704 KB	Execution timed out (wall clock limit exceeded)
25	Execution timed out	1000 ms	152024 KB	Execution timed out
26	Execution timed out	1000 ms	0 KB	Execution timed out
27	Execution timed out	1000 ms	246040 KB	Execution timed out
28	Runtime error	753 ms	75240 KB	Execution timed out (wall clock limit exceeded)
29	Execution timed out	1000 ms	128456 KB	Execution timed out
30	Execution timed out	1000 ms	143312 KB	Execution timed out
31	Runtime error	946 ms	79332 KB	Execution timed out (wall clock limit exceeded)
32	Execution timed out	1000 ms	91476 KB	Execution timed out
33	Runtime error	373 ms	50256 KB	Execution timed out (wall clock limit exceeded)
34	Execution timed out	1000 ms	0 KB	Execution timed out
35	Runtime error	803 ms	77220 KB	Execution timed out (wall clock limit exceeded)
36	Execution timed out	1000 ms	213728 KB	Execution timed out
37	Runtime error	666 ms	61004 KB	Execution timed out (wall clock limit exceeded)
38	Execution timed out	1000 ms	167396 KB	Execution timed out
39	Runtime error	606 ms	62588 KB	Execution timed out (wall clock limit exceeded)
40	Execution timed out	1000 ms	136772 KB	Execution timed out
41	Execution timed out	1000 ms	145424 KB	Execution timed out
42	Execution timed out	1000 ms	210824 KB	Execution timed out

답안 #31855

Compilation message

Subtask #1 10.0 / 20.0

Subtask #2 10.0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
10.0 / 20.0

Subtask #2
10.0 / 20.0

Subtask #3
0 / 60.0