| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 256315 | 2020-08-02T14:15:40 Z | Saboon | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 1000 ms | 214520 KB |
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
const int maxn = 1e7 + 10;
short cnt[maxn];
int last[maxn], pre[maxn], p[maxn];
int Q[maxn], tail, head;
int dp[maxn];
bitset<maxn> mark;
int main(){
ios_base::sync_with_stdio(false);
int m, q;
scanf("%d%d", &m, &q);
int sz = 0;
memset(last, -1, sizeof last);
int mxmp = 0;
int tof = 1;
while (m --){
int x;
scanf("%d", &x);
if (mark[x])
continue;
if (tof <= maxn)
tof *= x;
mxmp = max(mxmp, x);
mark[x] = 1;
cnt[0] ++;
p[sz] = x, pre[sz] = last[x], last[x] = sz ++;
}
Q[head++] = 0;
int n = 1000*1000*10;
int mxm = min(n+1,tof);
for (int i = 1; i < mxm; i++){
while (last[i] != -1){
int idx = last[i];
cnt[i-p[idx]] --;
if (tail == head or Q[head-1] != i)
Q[head++] = i;
cnt[i] ++;
if (i+p[idx] <= n){
p[sz] = p[idx], pre[sz] = last[i+p[idx]], last[i+p[idx]] = sz ++;
if (sz == maxn)
sz = 0;
}
last[i] = pre[last[i]];
}
if (tail == 0){
if (i >= mxmp)
tail ++;
else
cnt[0] = 1;
}
while (tail < head and cnt[Q[tail]] == 0)
tail ++;
dp[i] = dp[Q[tail]] + 1;
}
while (q --){
int x;
scanf("%d", &x);
if (x >= mxm)
printf("oo\n");
else
printf("%d\n", dp[x]);
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 21 ms | 39552 KB | Output is correct |
| 2 | Correct | 273 ms | 204948 KB | Output is correct |
| 3 | Correct | 26 ms | 43384 KB | Output is correct |
| 4 | Correct | 108 ms | 107080 KB | Output is correct |
| 5 | Correct | 141 ms | 131832 KB | Output is correct |
| 6 | Correct | 21 ms | 39552 KB | Output is correct |
| 7 | Correct | 26 ms | 43392 KB | Output is correct |
| 8 | Correct | 45 ms | 55416 KB | Output is correct |
| 9 | Correct | 332 ms | 208632 KB | Output is correct |
| 10 | Correct | 357 ms | 209528 KB | Output is correct |
| 11 | Correct | 292 ms | 203896 KB | Output is correct |
| 12 | Correct | 100 ms | 104696 KB | Output is correct |
| 13 | Correct | 529 ms | 212984 KB | Output is correct |
| 14 | Correct | 527 ms | 212984 KB | Output is correct |
| 15 | Correct | 265 ms | 204152 KB | Output is correct |
| 16 | Correct | 252 ms | 204920 KB | Output is correct |
| 17 | Correct | 155 ms | 132152 KB | Output is correct |
| 18 | Correct | 116 ms | 107132 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 170 ms | 118520 KB | Output is correct |
| 2 | Correct | 203 ms | 126840 KB | Output is correct |
| 3 | Correct | 952 ms | 213364 KB | Output is correct |
| 4 | Correct | 213 ms | 152564 KB | Output is correct |
| 5 | Correct | 560 ms | 207864 KB | Output is correct |
| 6 | Correct | 224 ms | 178040 KB | Output is correct |
| 7 | Correct | 170 ms | 118520 KB | Output is correct |
| 8 | Correct | 207 ms | 146552 KB | Output is correct |
| 9 | Correct | 700 ms | 209912 KB | Output is correct |
| 10 | Correct | 944 ms | 213368 KB | Output is correct |
| 11 | Correct | 844 ms | 213112 KB | Output is correct |
| 12 | Correct | 351 ms | 206328 KB | Output is correct |
| 13 | Correct | 145 ms | 128760 KB | Output is correct |
| 14 | Correct | 214 ms | 152568 KB | Output is correct |
| 15 | Correct | 705 ms | 212216 KB | Output is correct |
| 16 | Correct | 208 ms | 126712 KB | Output is correct |
| 17 | Correct | 542 ms | 212472 KB | Output is correct |
| 18 | Correct | 758 ms | 210692 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 909 ms | 213240 KB | Output is correct |
| 2 | Execution timed out | 1062 ms | 213624 KB | Time limit exceeded |
| 3 | Correct | 991 ms | 213828 KB | Output is correct |
| 4 | Correct | 418 ms | 208248 KB | Output is correct |
| 5 | Correct | 282 ms | 127352 KB | Output is correct |
| 6 | Correct | 573 ms | 211704 KB | Output is correct |
| 7 | Correct | 534 ms | 204792 KB | Output is correct |
| 8 | Correct | 824 ms | 213208 KB | Output is correct |
| 9 | Correct | 800 ms | 213240 KB | Output is correct |
| 10 | Correct | 403 ms | 203888 KB | Output is correct |
| 11 | Correct | 324 ms | 188404 KB | Output is correct |
| 12 | Correct | 525 ms | 211352 KB | Output is correct |
| 13 | Correct | 799 ms | 212908 KB | Output is correct |
| 14 | Correct | 422 ms | 211320 KB | Output is correct |
| 15 | Correct | 607 ms | 212856 KB | Output is correct |
| 16 | Correct | 611 ms | 213240 KB | Output is correct |
| 17 | Correct | 649 ms | 209092 KB | Output is correct |
| 18 | Execution timed out | 1048 ms | 214008 KB | Time limit exceeded |
| 19 | Correct | 215 ms | 151780 KB | Output is correct |
| 20 | Execution timed out | 1095 ms | 214112 KB | Time limit exceeded |
| 21 | Correct | 468 ms | 212904 KB | Output is correct |
| 22 | Execution timed out | 1101 ms | 214520 KB | Time limit exceeded |
| 23 | Correct | 251 ms | 131976 KB | Output is correct |
| 24 | Correct | 189 ms | 121848 KB | Output is correct |
| 25 | Correct | 442 ms | 207224 KB | Output is correct |
| 26 | Correct | 432 ms | 208632 KB | Output is correct |
| 27 | Execution timed out | 1109 ms | 210652 KB | Time limit exceeded |
| 28 | Correct | 204 ms | 144888 KB | Output is correct |
| 29 | Correct | 783 ms | 211192 KB | Output is correct |
| 30 | Correct | 682 ms | 209672 KB | Output is correct |
| 31 | Correct | 241 ms | 149848 KB | Output is correct |
| 32 | Correct | 279 ms | 165648 KB | Output is correct |
| 33 | Correct | 153 ms | 112028 KB | Output is correct |
| 34 | Correct | 542 ms | 205048 KB | Output is correct |
| 35 | Correct | 224 ms | 147716 KB | Output is correct |
| 36 | Execution timed out | 1041 ms | 214360 KB | Time limit exceeded |
| 37 | Correct | 283 ms | 127608 KB | Output is correct |
| 38 | Correct | 595 ms | 212028 KB | Output is correct |
| 39 | Correct | 207 ms | 128632 KB | Output is correct |
| 40 | Correct | 538 ms | 210304 KB | Output is correct |
| 41 | Correct | 609 ms | 208608 KB | Output is correct |
| 42 | Correct | 638 ms | 214056 KB | Output is correct |