Submission #31857

#	Time	Username	Problem	Language	Result	Execution time	Memory
31857		minhtung0404	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	58.57 / 100	789 ms	80532 KiB

brunhilda

#include<bits/stdc++.h>
const int N = 1e5 + 5;
const int M = 1e7 + 5;
const int inf = 1e9;
using namespace std;

int n, q, p[N], m, prime[M], ans[M], cnt = 1, ct;

int main(){
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++){
        int z = p[i];
        for (int j = 0; j < M; j+=z) prime[j] = max(prime[j], z);
    }
    for (int i = 1; i < M; i++) ans[i] = -inf;
    while(ct < M){
        while(cnt < ct + prime[ct] && cnt < M) ans[cnt] = ans[ct] + 1, cnt++;
        ct++;
    }
    while(q--){
        cin >> m;
        if (ans[m] <= 0) cout << "oo\n";
        else cout << ans[m] << "\n";
    }
}

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