# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
134091 | wzy | Brunhilda’s Birthday (BOI13_brunhilda) | C++11 | 460 ms | 118776 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 100002;
#define pii pair<int,int>
const int MX = 10000005;
int primes[N] ;
int m , q;
int dp[MX];
int adj[MX];
int vl[MX];
int dq[MX];
int currx = -1;
// valores formam sequencia (0 , 1 , 2, 3 ,...)
// pega o menor multiplo menor que i
int32_t main(){
scanf("%d%d" , &m , &q);
for(int i = 0 ; i < MX ;i ++){
dp[i] = 1000000000;
adj[i] = -1;
dq[i] = -1;
}
for(int i = 0 ; i < m ; i ++){
scanf("%d" , &primes[i]);
vl[++currx] = primes[i];
adj[currx] = dq[0];
dq[0] = currx;
}
dp[0] = 0;
int curr = 0;
for(int i = 0 ; i < MX ; i ++){
int w = dq[i];
while(w != -1){
int u = i + vl[w];
curr = max(curr, i+1);
curr = min(curr , MX - 1);
// if(i < 8){
// cout<<i<<" " <<w <<" " << u <<endl;
// }
for(int j = curr; j < min(u , MX) ; j++){
dp[j] = dp[i] + 1;
}
curr = max(curr, u);
curr = min(curr , MX - 1);
int wx = adj[w];
if(u < MX){
adj[w] = dq[u];
dq[u] = w;
}
w = wx;
}
}
for(int i = 0 ; i < q; i ++){
int x;
scanf("%d" , &x);
int u = dp[x];
if(u >= 1000000000){
printf("oo\n");
}
else{
printf("%d\n" , u);
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |