| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1079769 | GusterGoose27 | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 4e5+5;//4e5+5;
const ll MAXS = 1e18;
const int MAXB = 25; // will always terminate after 2^24 steps
const int sskip = 3;
vector<int> s, p, w, l;
int n;
struct step {
ll st, m; int f; // strength_gain, final, min to beat
step() {}
step(int i, int b) { // bucket id
if (i == n) {
st = 0;
f = n;
m = MAXS;
}
else {
int lcut = (1<<b);
if (lcut >= s[i]) {
st = s[i];
f = w[i];
m = MAXS;
}
else {
st = p[i];
f = l[i];
m = s[i];
}
}
// if (i == 24 && b == 9) cerr << "1 " << m << '\n';
// assert(m != 0);
// assert(f <= n);
}
step(step &a, step &b) {
st = min(MAXS, a.st+b.st);
f = b.f;
// m = min(a.m, (int)max(0ll, b.m-a.st));
m = min(a.m, max(0ll, b.m-a.st));
// assert(f <= n);
}
};
step lift[MAXB/sskip+1][MAXB][MAXN]; // cutoff, lift num, start
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
n = N;
s = S;
p = P;
w = W;
l = L;
for (int c = 0; c <= MAXB/sskip; c++) {
for (int i = 0; i <= n; i++) lift[c][0][i] = step(i, sskip*c);
// if (c == 9) cerr << lift[9][0][24].m << '\n';
for (int b = 1; b < MAXB; b++) {
for (int i = 0; i <= n; i++) lift[c][b][i] = step(lift[c][b-1][i], lift[c][b-1][lift[c][b-1][i].f]);
}
}
// cerr << lift[9][0][24].m << '\n';
}
ll simulate2(int x, ll z) {
// cerr << x << ' ' << z << '\n';
assert(x <= n);
if (x == n) return z;
int c = (z >= (1ll<<(MAXB-1)) ? MAXB-1 : 31-__builtin_clz(z));
// cerr << c << ' ' << z << '\n';
if (c == MAXB-1) return lift[c/sskip][MAXB-1][x].st + z;
for (int b = MAXB-1; b >= 0; b--) {
if (z < lift[c/sskip][b][x].m) return simulate2(lift[c/sskip][b][x].f, lift[c/sskip][b][x].st+z);
}
// if (z < s[x]) return -1;
// if (z < s[x]) {
// cerr << c << ' ' << z << ' ' << n << ' ' << x << '\n';
// cerr << lift[c][0][x].m << ' ' << s[x] << '\n';
// assert(false);
// }
assert(z >= s[x]);
return simulate2(w[x], z + s[x]);
}
ll simulate(int x, int z) {
// cerr << lift[9][0][24].m << '\n';
return simulate2(x, z);
}