Submission #31851

#	Time	Username	Problem	Language	Result	Execution time	Memory
31851		minhtung0404	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	35.56 / 100	413 ms	80692 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(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> p[i];
    sort(p+1, p+1+n);
    for (int i = 1; i <= n; i++){
        int z = p[i];
        for (int j = 0; j < M; j+=z){
            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: 15.555555555555555 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 60