Submission #31865

#	Time	Username	Problem	Language	Result	Execution time	Memory
31865		user202729	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	61.43 / 100	793 ms	80932 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;
    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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 21.428571428571427 / 60