| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 745306 | arthur_nascimento | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define lg 25
#define maxn 300300
#define inf (1e9)
#define debug
#define ll long long
int jmp[lg][19][maxn];
ll inc[lg][19][maxn];
int least[lg][19][maxn];
vector<int> strength, inc_lose, go_win, go_lose;
int n;
void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
//for(int i=0;i<N;i++) if(s[i] != 642842 ) printf("! %d -> %d %d, %d %d\n",i,w[i],l[i],s[i],p[i]);
n = N;
strength = s;
inc_lose = p;
go_win = w;
go_lose = l;
strength.pb(0);
inc_lose.pb(0);
go_win.pb(n);
go_lose.pb(n);
debug("ini!\n");
for(int k=0;k<lg;k++){
for(int i=0;i<n;i++){
if(strength[i] <= (1<<k))
jmp[k][0][i] = go_win[i],
inc[k][0][i] = strength[i],
least[k][0][i] = inf;
else
jmp[k][0][i] = go_lose[i],
inc[k][0][i] = inc_lose[i],
least[k][0][i] = strength[i];
if(k == 0)
debug("%d -> %d\n",i,jmp[k][0][i]);
if(jmp[k][0][i] == n)
least[k][0][i] = -1;
}
for(int j=1;j<19;j++)
for(int i=0;i<n;i++){
jmp[k][j][i] = jmp[k][j-1][jmp[k][j-1][i]],
inc[k][j][i] = inc[k][j-1][i] + inc[k][j-1][ jmp[k][j-1][i] ] ,
least[k][j][i] = max(0ll, min( (ll)least[k][j-1][i], least[k][j-1][ jmp[k][j-1][i] ] - inc[k][j-1][i] ));
if(least[k][j-1][i] > 1e8 && least[k][j-1][ jmp[k][j-1][i] ] > 1e8)
least[k][j][i] = 1e9;
}
}
return;
}
long long simulate(int x, int z0) {
ll z = z0;
while(x < n){
ll aux = z;
int k = 0;
while(aux > 1)
aux /= 2, k++;
k = min(k,24);
debug("x %d z %d k %d\n",x,z,k);
//for(int i=0;i<n;i++)
//debug("k %d i %d -> %d\n",k,i,jmp[k][0][i]);
debug("\n");
for(int j=18;j>=0;j--)
if(least[k][j][x] > z || least[k][j][x] > 1e8){
z += inc[k][j][x];
debug("%d jmp %d to %d add %d\n",x,1<<j,jmp[k][j][x],inc[k][j][x]);
x = jmp[k][j][x];
}
debug("z %d x %d stx %d\n",z,x,strength[x]);
// assert(z >= strength[x]);
//if(!((strength[x] >= (1<<k) || go_win[x] == n))) return 0;
if(z >= strength[x])
z += strength[x],
x = go_win[x];
else
z += inc_lose[x],
x = go_lose[x];
}
//printf("ans %d\n",z);
return z;
}