Submission #754248

#	Time	Username	Problem	Language	Result	Execution time	Memory
754248		phoebe	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	377 ms	33248 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("03")

#define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;

const int maxn = 1e8 + 10;

signed main(){
    int m, q; cin >> m >> q;
    int p[m]; FOR(i, m) cin >> p[i];
    vector<int> x; int mx = LLINF;
    int last = 1; x.PB(1);
    while (last < maxn){
        int next = -1;
        FOR(i, m){
            int val = ((last - 1) / p[i] + 1) * p[i];
            next = max(next, val);
        }
        x.PB(next);
        if (next == last){
            mx = next;
            break;
        }
        last = next;
    }
    while (q--){
        int n; cin >> n;
        if (n >= mx){
            cout << "oo" << endl;
            continue;
        }
        int idx = upper_bound(ALL(x), n) - x.begin();
        cout << idx << endl;
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60