Submission #632938

#	Time	Username	Problem	Language	Result	Execution time	Memory
632938		minhnhatnoe	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	213 ms	83260 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e7+10;

int stepptr = 1;
int step[MAXN], dist[MAXN];
void build_gp(int *prs, int m){
    int *gp = dist;
    fill(gp, gp+MAXN, 1);

    int *lp = step;
    for (int i=0; i<m; i++){
        gp[prs[i]] = prs[i];
    }
    vector<int> pr;
    for (int i=2; i<MAXN; i++){
        if (lp[i] == 0){
            lp[i] = i;
            pr.push_back(i);
        }
        for (int j=0; j<pr.size() && pr[j] <= lp[i] && pr[j] * i < MAXN; j++){
            lp[pr[j] * i] = pr[j];
            gp[pr[j] * i] = max(gp[pr[j]], gp[i]);
        }
    }
    for (int i=0; i<MAXN-1; i++){
        dist[i] = gp[i+1] - 1;
    }

}
void build_dist(int m){
    int prs[m];
    for (int i=0; i<m; i++) cin >> prs[i];
    sort(prs, prs + m);
    m = unique(prs, prs + m) - prs;
    build_gp(prs, m);
    for (int i=0; i<m; i++){
        dist[MAXN-1] = max(dist[MAXN-1], (MAXN-1) % prs[i]);
    }
    for (int i=MAXN-2; i>=0; i--){
        dist[i] = max(dist[i], dist[i+1]-1);
    }
}
void build_step(){
    step[0] = 0;
    for (; stepptr<MAXN && dist[stepptr]; stepptr++){
        step[stepptr] = step[stepptr - dist[stepptr]] + 1;
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int m, q; cin >> m >> q;
    build_dist(m);
    build_step();
    for (int i=0; i<q; i++){
        int val; cin >> val;
        if (val >= stepptr){
            cout << "oo\n";
        }
        else{
            cout << step[val] << "\n";
        }
    }
}

Compilation message (stderr)

brunhilda.cpp: In function 'void build_gp(int*, int)':
brunhilda.cpp:22:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int j=0; j<pr.size() && pr[j] <= lp[i] && pr[j] * i < MAXN; j++){
      |                       ~^~~~~~~~~~

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