Submission #535486

#	Time	Username	Problem	Language	Result	Execution time	Memory
535486		Baray	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	443 ms	159368 KiB

brunhilda

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define N 10000005

int sieve[N], cost[N];
int n, q;

signed main() {
    cin >> n >> q;
    
    vector<int> a(n);
    int child, l = 1, mx = 0, p;

    for (int i = 0; i < n; i++) {
        cin >> p;
        mx = max(mx, p);

        for (int j = p; j < N; j += p) {
            sieve[j] = p;
        }
    }

    int cur = mx, next = 0, cur_cost = 1;

    for (int i = 0; i < N; i++) {
        if (i >= cur) {
            if (next > cur) {
                cur = next;
                cur_cost++;
            }
            else break;
        }
        
        cost[i] = cur_cost;
        if (sieve[i]) next = max(next, i + sieve[i]);
    }

    while (q--) {
        cin >> p;

        if (cost[p] == 0) {
            cout << "oo\n";
            continue;
        }

        cout << cost[p] << "\n";
    }
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:17:9: warning: unused variable 'child' [-Wunused-variable]
   17 |     int child, l = 1, mx = 0, p;
      |         ^~~~~
brunhilda.cpp:17:16: warning: unused variable 'l' [-Wunused-variable]
   17 |     int child, l = 1, mx = 0, p;
      |                ^

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