| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 256257 | 2020-08-02T12:34:34 Z | Saboon | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 844 ms | 262148 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;
int cnt[maxn];
int last[maxn], pre[9*maxn], p[9*maxn];
int Q[maxn], CQ[maxn], tail, head;
int dp[maxn];
int main(){
ios_base::sync_with_stdio(false);
int m, q;
cin >> m >> q;
int sz = 0;
memset(last, -1, sizeof last);
for (int i = 0; i < m; i++){
int x;
cin >> x;
p[sz] = x, pre[sz] = last[0], last[0] = sz ++;
}
int n = 1000*1000*10;
int mxm = n+1;
for (int i = 0; i <= n; i++){
while (last[i] != -1){
int idx = last[i];
if (i > 0)
cnt[i-p[idx]] ++;
if (tail == head or Q[head-1] != i)
Q[head++] = i;
CQ[head-1] ++;
if (i+p[idx] <= n)
p[sz] = p[idx], pre[sz] = last[i+p[idx]], last[i+p[idx]] = sz ++;
last[i] = pre[last[i]];
}
while (tail < head and cnt[Q[tail]] == CQ[tail])
tail ++;
if (i > 0){
if (Q[tail] == i){
dp[i] = -1;
mxm = i;
break;
}
dp[i] = dp[Q[tail]] + 1;
}
}
while (q --){
int x;
cin >> x;
if (x >= mxm)
cout << "oo\n";
else
cout << dp[x] << '\n';
}
}
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 23 ms | 39544 KB | Output is correct |
| 2 | Correct | 271 ms | 255224 KB | Output is correct |
| 3 | Correct | 26 ms | 44536 KB | Output is correct |
| 4 | Correct | 143 ms | 129528 KB | Output is correct |
| 5 | Correct | 165 ms | 161784 KB | Output is correct |
| 6 | Correct | 23 ms | 39544 KB | Output is correct |
| 7 | Correct | 27 ms | 44536 KB | Output is correct |
| 8 | Correct | 46 ms | 59768 KB | Output is correct |
| 9 | Runtime error | 341 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 | Runtime error | 347 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 | Correct | 319 ms | 258040 KB | Output is correct |
| 12 | Correct | 136 ms | 126200 KB | Output is correct |
| 13 | Runtime error | 394 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 | Runtime error | 401 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 | Correct | 306 ms | 251000 KB | Output is correct |
| 16 | Correct | 275 ms | 255352 KB | Output is correct |
| 17 | Correct | 182 ms | 161912 KB | Output is correct |
| 18 | Correct | 150 ms | 129528 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 187 ms | 144760 KB | Output is correct |
| 2 | Correct | 229 ms | 154744 KB | Output is correct |
| 3 | Runtime error | 692 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 | Correct | 244 ms | 188028 KB | Output is correct |
| 5 | Runtime error | 573 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 | Correct | 272 ms | 221048 KB | Output is correct |
| 7 | Correct | 179 ms | 144760 KB | Output is correct |
| 8 | Correct | 216 ms | 180220 KB | Output is correct |
| 9 | Runtime error | 598 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 | Runtime error | 764 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 | Runtime error | 604 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 | Runtime error | 374 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 | Correct | 173 ms | 157816 KB | Output is correct |
| 14 | Correct | 229 ms | 188032 KB | Output is correct |
| 15 | Runtime error | 665 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 | Correct | 223 ms | 154744 KB | Output is correct |
| 17 | Runtime error | 411 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 | Runtime error | 608 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 619 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Runtime error | 669 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 | Runtime error | 637 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 | Runtime error | 380 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 | Correct | 465 ms | 156028 KB | Output is correct |
| 6 | Runtime error | 436 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 | Correct | 657 ms | 252280 KB | Output is correct |
| 8 | Runtime error | 615 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 | Runtime error | 573 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 | Runtime error | 405 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 | Correct | 375 ms | 230916 KB | Output is correct |
| 12 | Runtime error | 448 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 | Runtime error | 607 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 | Runtime error | 356 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 | Runtime error | 462 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 | Runtime error | 471 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 | Runtime error | 702 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 | Runtime error | 706 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 19 | Correct | 288 ms | 187256 KB | Output is correct |
| 20 | Runtime error | 645 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 21 | Runtime error | 387 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 22 | Runtime error | 844 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 23 | Correct | 461 ms | 161784 KB | Output is correct |
| 24 | Correct | 378 ms | 147832 KB | Output is correct |
| 25 | Runtime error | 391 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 26 | Runtime error | 387 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 27 | Runtime error | 769 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 28 | Correct | 418 ms | 177656 KB | Output is correct |
| 29 | Runtime error | 832 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 30 | Runtime error | 605 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 31 | Correct | 410 ms | 183800 KB | Output is correct |
| 32 | Correct | 463 ms | 203128 KB | Output is correct |
| 33 | Correct | 336 ms | 135032 KB | Output is correct |
| 34 | Correct | 634 ms | 252152 KB | Output is correct |
| 35 | Correct | 424 ms | 181112 KB | Output is correct |
| 36 | Runtime error | 640 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 37 | Correct | 457 ms | 156024 KB | Output is correct |
| 38 | Runtime error | 488 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 39 | Correct | 381 ms | 156688 KB | Output is correct |
| 40 | Runtime error | 443 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 41 | Runtime error | 656 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 42 | Runtime error | 419 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |