| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 501560 | ETK | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeon.h"
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pb push_back
using namespace std;
const int inf = 0x3f3f3f3f,N = 4e5 + 5,B = 16,L = 7;
//The key observation is that every time we win our damage doubles
struct info{
//next place and the attack you need to win a game
int nxt,atk;
//overall attack we gained
ll sum;
info operator + (const info a)const{
int res;
if(a.atk == inf)res = atk;
else res = max(0ll,min((ll)atk,a.atk - sum));
return (info){a.nxt,res,sum + a.sum};
}
}f[L][25][N];
int n,powB[L];
vi s,p,w,l;
ll simulate(int x,int z){
int i = 0;
while(114514){
if(i + 1 < L && z > powB[i+1]) ++i;
for(int j = 24;j >= 0;j--){
info now = f[i][j][x];
if(now.nxt == n)continue;//jumping too far
if(now.atk != inf)continue;//
if(now.atk <= z)continue;//already winning
z += now.sum, x = now.nxt;
}
if(z >= s[x]) z += s[x], x = w[x];
else z += p[x], x = l[x];
if(x == n)return z;
}
}
void prework(int X,int k){
for(int i = 0;i < n;i++){
if(X >= s[i]){
f[k][0][i] = (info){w[i],inf,s[i]};
}else f[k][0][i] = (info){l[i],s[i],p[i]};
}
for(int j = 1;j < 25;j++)for(int i = 0;i < n;i++){
info t = f[k][j-1][i];
f[k][j][i] = t + f[k][j-1][t.nxt];
}
}
void init(int _n,vi _s,vi _p,vi _w,vi _l){
n = _n,s = _s,p = _p,w = _w,l = _l;
w.pb(n),l.pb(n);
powB[0] = 1;
for(int d = 0;d < L;d++){
prework(powB[d],d);
powB[d+1] = powB[d] * B;
}
}