| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 134091 | 2019-07-22T04:17:40 Z | wzy | Brunhilda’s Birthday (BOI13_brunhilda) | C++11 | 460 ms | 118776 KB |
#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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 154 ms | 117780 KB | Output is correct |
| 2 | Correct | 210 ms | 117832 KB | Output is correct |
| 3 | Correct | 206 ms | 117880 KB | Output is correct |
| 4 | Correct | 156 ms | 117880 KB | Output is correct |
| 5 | Correct | 211 ms | 117668 KB | Output is correct |
| 6 | Correct | 155 ms | 117664 KB | Output is correct |
| 7 | Correct | 202 ms | 117968 KB | Output is correct |
| 8 | Correct | 217 ms | 117752 KB | Output is correct |
| 9 | Correct | 259 ms | 117788 KB | Output is correct |
| 10 | Correct | 274 ms | 117828 KB | Output is correct |
| 11 | Correct | 248 ms | 117752 KB | Output is correct |
| 12 | Correct | 151 ms | 117752 KB | Output is correct |
| 13 | Correct | 318 ms | 117680 KB | Output is correct |
| 14 | Correct | 342 ms | 117868 KB | Output is correct |
| 15 | Correct | 225 ms | 117780 KB | Output is correct |
| 16 | Correct | 216 ms | 117888 KB | Output is correct |
| 17 | Correct | 205 ms | 117780 KB | Output is correct |
| 18 | Correct | 155 ms | 117816 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 186 ms | 117956 KB | Output is correct |
| 2 | Correct | 209 ms | 118392 KB | Output is correct |
| 3 | Correct | 391 ms | 118236 KB | Output is correct |
| 4 | Correct | 213 ms | 117752 KB | Output is correct |
| 5 | Correct | 310 ms | 118184 KB | Output is correct |
| 6 | Correct | 210 ms | 117788 KB | Output is correct |
| 7 | Correct | 194 ms | 117916 KB | Output is correct |
| 8 | Correct | 199 ms | 117672 KB | Output is correct |
| 9 | Correct | 361 ms | 118344 KB | Output is correct |
| 10 | Correct | 396 ms | 118332 KB | Output is correct |
| 11 | Correct | 369 ms | 118044 KB | Output is correct |
| 12 | Correct | 270 ms | 117872 KB | Output is correct |
| 13 | Correct | 177 ms | 117752 KB | Output is correct |
| 14 | Correct | 220 ms | 117812 KB | Output is correct |
| 15 | Correct | 395 ms | 118068 KB | Output is correct |
| 16 | Correct | 209 ms | 118520 KB | Output is correct |
| 17 | Correct | 315 ms | 117880 KB | Output is correct |
| 18 | Correct | 460 ms | 118452 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 437 ms | 118176 KB | Output is correct |
| 2 | Correct | 395 ms | 118280 KB | Output is correct |
| 3 | Correct | 458 ms | 118308 KB | Output is correct |
| 4 | Correct | 322 ms | 118008 KB | Output is correct |
| 5 | Correct | 253 ms | 118648 KB | Output is correct |
| 6 | Correct | 359 ms | 118104 KB | Output is correct |
| 7 | Correct | 314 ms | 118776 KB | Output is correct |
| 8 | Correct | 392 ms | 118192 KB | Output is correct |
| 9 | Correct | 372 ms | 118264 KB | Output is correct |
| 10 | Correct | 283 ms | 117836 KB | Output is correct |
| 11 | Correct | 261 ms | 117872 KB | Output is correct |
| 12 | Correct | 392 ms | 117880 KB | Output is correct |
| 13 | Correct | 381 ms | 118252 KB | Output is correct |
| 14 | Correct | 337 ms | 118264 KB | Output is correct |
| 15 | Correct | 362 ms | 117956 KB | Output is correct |
| 16 | Correct | 350 ms | 117880 KB | Output is correct |
| 17 | Correct | 327 ms | 118272 KB | Output is correct |
| 18 | Correct | 408 ms | 118176 KB | Output is correct |
| 19 | Correct | 202 ms | 117872 KB | Output is correct |
| 20 | Correct | 405 ms | 118252 KB | Output is correct |
| 21 | Correct | 319 ms | 118336 KB | Output is correct |
| 22 | Correct | 457 ms | 118732 KB | Output is correct |
| 23 | Correct | 247 ms | 118264 KB | Output is correct |
| 24 | Correct | 214 ms | 118136 KB | Output is correct |
| 25 | Correct | 318 ms | 118036 KB | Output is correct |
| 26 | Correct | 331 ms | 118068 KB | Output is correct |
| 27 | Correct | 447 ms | 118564 KB | Output is correct |
| 28 | Correct | 217 ms | 118136 KB | Output is correct |
| 29 | Correct | 382 ms | 118696 KB | Output is correct |
| 30 | Correct | 349 ms | 118520 KB | Output is correct |
| 31 | Correct | 246 ms | 117944 KB | Output is correct |
| 32 | Correct | 263 ms | 118068 KB | Output is correct |
| 33 | Correct | 200 ms | 118008 KB | Output is correct |
| 34 | Correct | 345 ms | 118648 KB | Output is correct |
| 35 | Correct | 223 ms | 118116 KB | Output is correct |
| 36 | Correct | 438 ms | 118672 KB | Output is correct |
| 37 | Correct | 251 ms | 118684 KB | Output is correct |
| 38 | Correct | 356 ms | 118092 KB | Output is correct |
| 39 | Correct | 227 ms | 117980 KB | Output is correct |
| 40 | Correct | 338 ms | 118108 KB | Output is correct |
| 41 | Correct | 317 ms | 118648 KB | Output is correct |
| 42 | Correct | 345 ms | 118264 KB | Output is correct |