| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 256263 | 2020-08-02T12:44:56 Z | Saboon | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 818 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){
if (sz == 9*maxn-1)
exit(0);
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 | 24 ms | 39680 KB | Output is correct |
| 2 | Correct | 271 ms | 255224 KB | Output is correct |
| 3 | Correct | 29 ms | 44536 KB | Output is correct |
| 4 | Correct | 162 ms | 129528 KB | Output is correct |
| 5 | Correct | 177 ms | 161784 KB | Output is correct |
| 6 | Correct | 28 ms | 39552 KB | Output is correct |
| 7 | Correct | 26 ms | 44544 KB | Output is correct |
| 8 | Correct | 51 ms | 59772 KB | Output is correct |
| 9 | Runtime error | 344 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 | Runtime error | 369 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 | Correct | 341 ms | 258040 KB | Output is correct |
| 12 | Correct | 120 ms | 126328 KB | Output is correct |
| 13 | Runtime error | 432 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 | Runtime error | 407 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 | Correct | 310 ms | 251128 KB | Output is correct |
| 16 | Correct | 271 ms | 255216 KB | Output is correct |
| 17 | Correct | 190 ms | 161912 KB | Output is correct |
| 18 | Correct | 167 ms | 129528 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 208 ms | 144760 KB | Output is correct |
| 2 | Correct | 252 ms | 154744 KB | Output is correct |
| 3 | Runtime error | 638 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 | Correct | 255 ms | 188024 KB | Output is correct |
| 5 | Runtime error | 534 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 | Correct | 237 ms | 220920 KB | Output is correct |
| 7 | Correct | 203 ms | 144760 KB | Output is correct |
| 8 | Correct | 217 ms | 180376 KB | Output is correct |
| 9 | Runtime error | 746 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 | Runtime error | 747 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 | Runtime error | 676 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 | Runtime error | 368 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 | Correct | 193 ms | 157688 KB | Output is correct |
| 14 | Correct | 237 ms | 188024 KB | Output is correct |
| 15 | Runtime error | 564 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 | Correct | 227 ms | 154616 KB | Output is correct |
| 17 | Runtime error | 415 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 | Runtime error | 611 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 605 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Runtime error | 809 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 | Runtime error | 629 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 | Runtime error | 402 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 | Correct | 475 ms | 156112 KB | Output is correct |
| 6 | Runtime error | 440 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 | Correct | 654 ms | 252220 KB | Output is correct |
| 8 | Runtime error | 615 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 | Runtime error | 688 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 | Runtime error | 430 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 | Correct | 373 ms | 231032 KB | Output is correct |
| 12 | Runtime error | 417 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 | Runtime error | 657 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 | Runtime error | 365 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 | Runtime error | 438 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 | Runtime error | 436 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 | Runtime error | 616 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 | Runtime error | 655 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 19 | Correct | 262 ms | 187256 KB | Output is correct |
| 20 | Runtime error | 636 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 21 | Runtime error | 398 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 22 | Runtime error | 704 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 23 | Correct | 479 ms | 161896 KB | Output is correct |
| 24 | Correct | 377 ms | 147960 KB | Output is correct |
| 25 | Runtime error | 395 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 26 | Runtime error | 422 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 27 | Runtime error | 802 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 28 | Correct | 436 ms | 177660 KB | Output is correct |
| 29 | Runtime error | 694 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 30 | Runtime error | 592 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 31 | Correct | 410 ms | 183672 KB | Output is correct |
| 32 | Correct | 509 ms | 203128 KB | Output is correct |
| 33 | Correct | 344 ms | 135084 KB | Output is correct |
| 34 | Correct | 818 ms | 252152 KB | Output is correct |
| 35 | Correct | 427 ms | 180960 KB | Output is correct |
| 36 | Runtime error | 780 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 37 | Correct | 473 ms | 156024 KB | Output is correct |
| 38 | Runtime error | 477 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 39 | Correct | 437 ms | 156536 KB | Output is correct |
| 40 | Runtime error | 487 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 41 | Runtime error | 631 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 42 | Runtime error | 412 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |