Submission #31855

#	Time	Username	Problem	Language	Result	Execution time	Memory
31855		user202729	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	20 / 100	1000 ms	246040 KiB

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 / 20
• Subtask 2: 10 / 20
• Subtask 3: 0 / 60