| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 256311 | 2020-08-02T14:09:28 Z | Saboon | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 1000 ms | 213880 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;
for (int i = 0; i < m; i++){
int x;
scanf("%d", &x);
if (mark[x])
continue;
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 = n+1;
for (int i = 1; i <= n; 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 ++;
if (Q[tail] == i){
dp[i] = -1;
mxm = i;
break;
}
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 | 252 ms | 204836 KB | Output is correct |
| 3 | Correct | 26 ms | 43384 KB | Output is correct |
| 4 | Correct | 121 ms | 107100 KB | Output is correct |
| 5 | Correct | 153 ms | 131844 KB | Output is correct |
| 6 | Correct | 21 ms | 39552 KB | Output is correct |
| 7 | Correct | 26 ms | 43384 KB | Output is correct |
| 8 | Correct | 45 ms | 55416 KB | Output is correct |
| 9 | Correct | 343 ms | 208760 KB | Output is correct |
| 10 | Correct | 371 ms | 209528 KB | Output is correct |
| 11 | Correct | 297 ms | 203896 KB | Output is correct |
| 12 | Correct | 106 ms | 104568 KB | Output is correct |
| 13 | Correct | 535 ms | 212856 KB | Output is correct |
| 14 | Correct | 543 ms | 212856 KB | Output is correct |
| 15 | Correct | 275 ms | 204152 KB | Output is correct |
| 16 | Correct | 263 ms | 205048 KB | Output is correct |
| 17 | Correct | 161 ms | 132088 KB | Output is correct |
| 18 | Correct | 126 ms | 107260 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 160 ms | 118648 KB | Output is correct |
| 2 | Correct | 217 ms | 126840 KB | Output is correct |
| 3 | Correct | 970 ms | 213628 KB | Output is correct |
| 4 | Correct | 215 ms | 152568 KB | Output is correct |
| 5 | Correct | 580 ms | 207992 KB | Output is correct |
| 6 | Correct | 226 ms | 177912 KB | Output is correct |
| 7 | Correct | 162 ms | 118620 KB | Output is correct |
| 8 | Correct | 199 ms | 146552 KB | Output is correct |
| 9 | Correct | 690 ms | 210120 KB | Output is correct |
| 10 | Correct | 955 ms | 213548 KB | Output is correct |
| 11 | Correct | 891 ms | 213112 KB | Output is correct |
| 12 | Correct | 360 ms | 206328 KB | Output is correct |
| 13 | Correct | 158 ms | 128760 KB | Output is correct |
| 14 | Correct | 220 ms | 152568 KB | Output is correct |
| 15 | Correct | 766 ms | 212216 KB | Output is correct |
| 16 | Correct | 242 ms | 127104 KB | Output is correct |
| 17 | Correct | 581 ms | 212452 KB | Output is correct |
| 18 | Correct | 816 ms | 210964 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 802 ms | 212992 KB | Output is correct |
| 2 | Correct | 967 ms | 213496 KB | Output is correct |
| 3 | Correct | 934 ms | 213624 KB | Output is correct |
| 4 | Correct | 422 ms | 207912 KB | Output is correct |
| 5 | Correct | 260 ms | 126968 KB | Output is correct |
| 6 | Correct | 556 ms | 211704 KB | Output is correct |
| 7 | Correct | 501 ms | 204536 KB | Output is correct |
| 8 | Correct | 786 ms | 212856 KB | Output is correct |
| 9 | Correct | 896 ms | 212984 KB | Output is correct |
| 10 | Correct | 383 ms | 203812 KB | Output is correct |
| 11 | Correct | 317 ms | 188280 KB | Output is correct |
| 12 | Correct | 512 ms | 211192 KB | Output is correct |
| 13 | Correct | 812 ms | 212600 KB | Output is correct |
| 14 | Correct | 421 ms | 211192 KB | Output is correct |
| 15 | Correct | 591 ms | 212728 KB | Output is correct |
| 16 | Correct | 615 ms | 212984 KB | Output is correct |
| 17 | Correct | 635 ms | 208888 KB | Output is correct |
| 18 | Correct | 988 ms | 213396 KB | Output is correct |
| 19 | Correct | 203 ms | 151420 KB | Output is correct |
| 20 | Execution timed out | 1033 ms | 213492 KB | Time limit exceeded |
| 21 | Correct | 471 ms | 212344 KB | Output is correct |
| 22 | Execution timed out | 1092 ms | 213560 KB | Time limit exceeded |
| 23 | Correct | 317 ms | 131416 KB | Output is correct |
| 24 | Correct | 196 ms | 121208 KB | Output is correct |
| 25 | Correct | 430 ms | 206712 KB | Output is correct |
| 26 | Correct | 415 ms | 207992 KB | Output is correct |
| 27 | Execution timed out | 1104 ms | 212228 KB | Time limit exceeded |
| 28 | Correct | 205 ms | 144376 KB | Output is correct |
| 29 | Correct | 772 ms | 210808 KB | Output is correct |
| 30 | Correct | 671 ms | 208968 KB | Output is correct |
| 31 | Correct | 239 ms | 149244 KB | Output is correct |
| 32 | Correct | 274 ms | 164988 KB | Output is correct |
| 33 | Correct | 155 ms | 111480 KB | Output is correct |
| 34 | Correct | 500 ms | 204408 KB | Output is correct |
| 35 | Correct | 215 ms | 147192 KB | Output is correct |
| 36 | Execution timed out | 1054 ms | 213880 KB | Time limit exceeded |
| 37 | Correct | 264 ms | 127096 KB | Output is correct |
| 38 | Correct | 552 ms | 211452 KB | Output is correct |
| 39 | Correct | 195 ms | 127992 KB | Output is correct |
| 40 | Correct | 497 ms | 209784 KB | Output is correct |
| 41 | Correct | 531 ms | 208120 KB | Output is correct |
| 42 | Correct | 602 ms | 213452 KB | Output is correct |