| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 453626 | flappybird | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
vector<pll> win, lose; //next
int nxt[9][40][404040], limit[9][40][404040];
ll delta[9][40][404040];
int N;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
ll i;
win.resize(N + 1);
lose.resize(N + 1);
for (i = 0; i < N; i++) {
win[i] = { w[i], s[i] };
lose[i] = { l[i], p[i] };
}
ll k;
for (k = 0; k < MAXI; k++) {
ll low, high;
low = 1 << (3 * k);
high = 1 << (3 * (k + 1));
for (i = 0; i < N; i++) {
if (s[i] < low) {
nxt[k][0][i] = win[i].first;
delta[k][0][i] = win[i].second;
limit[k][0][i] = INF;
}
else if (s[i] >= high) {
nxt[k][0][i] = lose[i].first;
delta[k][0][i] = lose[i].second;
limit[k][0][i] = s[i];
}
else {
nxt[k][0][i] = lose[i].first;
delta[k][0][i] = lose[i].second;
limit[k][0][i] = s[i];
}
}
nxt[k][0][N] = N;
delta[k][0][N] = 0;
limit[k][0][N] = INF;
ll j;
for (j = 1; j < k + 1; j++) {
for (i = 0; i <= N; i++) {
ll v = nxt[k][j - 1][i];
nxt[k][j][i] = nxt[k][j - 1][v];
delta[k][j][i] = delta[k][j - 1][i] + delta[k][j - 1][v];
limit[k][j][i] = (int)max(0LL, min((ll)limit[k][j - 1][v] - delta[k][j - 1][i], (ll)limit[k][j - 1][i]));
}
}
}
return;
}
ll get(ll x) {
return 0;
}
long long f(ll x, ll z) {
ll i;
for (i = 0; i < MAXI; i++) {
ll low, high;
high = 1 << (3 * (i + 1));
if (i == MAXI - 1) return z + get(x);
if (high <= z) continue;
ll k;
ll c = 1;
while (c) {
c = 0;
if (high <= z) break;
for (k = 3 * i + 2; k >= 0; k--) {
if (limit[i][k][x] > z) {
c = 1;
z += delta[i][k][x];
x = nxt[i][k][x];
}
if (high <= z) break;
if (x == N) return z;
}
if (high <= z) break;
if (c == 0) {
if (z >= win[x].second) z += win[x].second, x = win[x].first;
else z += lose[x].second, x = lose[x].first;
if (x == N) return z;
if (high <= z) break;
c = 1;
}
if (x == N) return z;
if (high <= z) break;
}
}
return z;
}
long long simulate(int x, int z) {
return f(x, z);
}