| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 243404 | 2020-07-01T02:50:38 Z | Lawliet | Brunhilda’s Birthday (BOI13_brunhilda) | C++17 | 378 ms | 80836 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 100010;
const int MAXN = 10000010;
const int INF = 1000000010;
int m, q;
int v[MAXM];
int dp[MAXN], mx[MAXN];
int getNext(int value, int p) { return value - value%p; }
int main()
{
scanf("%d %d",&m,&q);
for(int i = 1 ; i <= m ; i++)
scanf("%d",&v[i]);
for(int i = 1 ; i <= m ; i++)
for(int cur = v[i] ; cur < MAXN ; cur += v[i])
mx[cur] = max( mx[cur] , v[i] );
int mn = INF;
for(int i = 1 ; i <= m ; i++)
mn = min( mn , getNext( 10000000 , v[i] ) );
for(int i = MAXN - 1 ; i > 0 ; i--)
{
dp[i] = mn;
if( mx[i] != 0 ) mn = min( mn , getNext( i - 1 , mx[i] ) );
}
for(int i = 1 ; i < MAXN ; i++)
{
if( dp[i] == i ) dp[i] = INF;
else dp[i] = dp[ dp[i] ] + 1;
}
for(int i = 1 ; i <= q ; i++)
{
int p;
scanf("%d",&p);
if( dp[p] >= INF ) printf("oo\n");
else printf("%d\n",dp[p]);
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 114 ms | 78712 KB | Output is correct |
| 2 | Correct | 153 ms | 78584 KB | Output is correct |
| 3 | Correct | 132 ms | 78584 KB | Output is correct |
| 4 | Correct | 90 ms | 78692 KB | Output is correct |
| 5 | Correct | 122 ms | 78552 KB | Output is correct |
| 6 | Correct | 97 ms | 78584 KB | Output is correct |
| 7 | Correct | 141 ms | 78840 KB | Output is correct |
| 8 | Correct | 178 ms | 78584 KB | Output is correct |
| 9 | Correct | 169 ms | 78584 KB | Output is correct |
| 10 | Correct | 186 ms | 78560 KB | Output is correct |
| 11 | Correct | 169 ms | 78584 KB | Output is correct |
| 12 | Correct | 78 ms | 78584 KB | Output is correct |
| 13 | Correct | 265 ms | 78784 KB | Output is correct |
| 14 | Correct | 266 ms | 78716 KB | Output is correct |
| 15 | Correct | 180 ms | 78604 KB | Output is correct |
| 16 | Correct | 151 ms | 78712 KB | Output is correct |
| 17 | Correct | 126 ms | 78712 KB | Output is correct |
| 18 | Correct | 83 ms | 78712 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 105 ms | 78780 KB | Output is correct |
| 2 | Correct | 126 ms | 79712 KB | Output is correct |
| 3 | Correct | 305 ms | 79352 KB | Output is correct |
| 4 | Correct | 143 ms | 78584 KB | Output is correct |
| 5 | Correct | 223 ms | 79096 KB | Output is correct |
| 6 | Correct | 134 ms | 78584 KB | Output is correct |
| 7 | Correct | 103 ms | 78712 KB | Output is correct |
| 8 | Correct | 147 ms | 78584 KB | Output is correct |
| 9 | Correct | 254 ms | 79356 KB | Output is correct |
| 10 | Correct | 304 ms | 79432 KB | Output is correct |
| 11 | Correct | 290 ms | 78972 KB | Output is correct |
| 12 | Correct | 194 ms | 78784 KB | Output is correct |
| 13 | Correct | 94 ms | 78584 KB | Output is correct |
| 14 | Correct | 152 ms | 78652 KB | Output is correct |
| 15 | Correct | 287 ms | 79096 KB | Output is correct |
| 16 | Correct | 126 ms | 79656 KB | Output is correct |
| 17 | Correct | 265 ms | 78584 KB | Output is correct |
| 18 | Correct | 258 ms | 79864 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 274 ms | 79608 KB | Output is correct |
| 2 | Correct | 318 ms | 79388 KB | Output is correct |
| 3 | Correct | 323 ms | 79736 KB | Output is correct |
| 4 | Correct | 226 ms | 79612 KB | Output is correct |
| 5 | Correct | 169 ms | 80632 KB | Output is correct |
| 6 | Correct | 281 ms | 79736 KB | Output is correct |
| 7 | Correct | 247 ms | 80248 KB | Output is correct |
| 8 | Correct | 277 ms | 79608 KB | Output is correct |
| 9 | Correct | 272 ms | 79608 KB | Output is correct |
| 10 | Correct | 207 ms | 78840 KB | Output is correct |
| 11 | Correct | 189 ms | 78840 KB | Output is correct |
| 12 | Correct | 246 ms | 78968 KB | Output is correct |
| 13 | Correct | 308 ms | 79968 KB | Output is correct |
| 14 | Correct | 220 ms | 79992 KB | Output is correct |
| 15 | Correct | 261 ms | 78968 KB | Output is correct |
| 16 | Correct | 318 ms | 78968 KB | Output is correct |
| 17 | Correct | 246 ms | 79224 KB | Output is correct |
| 18 | Correct | 306 ms | 79352 KB | Output is correct |
| 19 | Correct | 120 ms | 78840 KB | Output is correct |
| 20 | Correct | 321 ms | 79864 KB | Output is correct |
| 21 | Correct | 246 ms | 79992 KB | Output is correct |
| 22 | Correct | 334 ms | 80632 KB | Output is correct |
| 23 | Correct | 170 ms | 79864 KB | Output is correct |
| 24 | Correct | 140 ms | 79636 KB | Output is correct |
| 25 | Correct | 255 ms | 79824 KB | Output is correct |
| 26 | Correct | 228 ms | 79608 KB | Output is correct |
| 27 | Correct | 346 ms | 80376 KB | Output is correct |
| 28 | Correct | 156 ms | 79736 KB | Output is correct |
| 29 | Correct | 378 ms | 80712 KB | Output is correct |
| 30 | Correct | 298 ms | 80376 KB | Output is correct |
| 31 | Correct | 202 ms | 79480 KB | Output is correct |
| 32 | Correct | 191 ms | 79608 KB | Output is correct |
| 33 | Correct | 120 ms | 79608 KB | Output is correct |
| 34 | Correct | 244 ms | 80248 KB | Output is correct |
| 35 | Correct | 158 ms | 79840 KB | Output is correct |
| 36 | Correct | 351 ms | 80504 KB | Output is correct |
| 37 | Correct | 182 ms | 80836 KB | Output is correct |
| 38 | Correct | 285 ms | 79608 KB | Output is correct |
| 39 | Correct | 161 ms | 79736 KB | Output is correct |
| 40 | Correct | 278 ms | 79736 KB | Output is correct |
| 41 | Correct | 228 ms | 80248 KB | Output is correct |
| 42 | Correct | 340 ms | 79832 KB | Output is correct |