| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 443271 | JvThunder | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
typedef long long ll;
using namespace std;
int N;
vector<int> S,P,W,L;
int base = 8;
const int nop = 15;
const int noa = 25;
const int sz = 400005;
ll jump[nop][noa][sz]; // 8^b,2^jump,pos
ll add[nop][noa][sz];
ll diff[nop][noa][sz];
ll mx[nop][noa][sz];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
S = s; P = p; W = w; L = l; N = n;
S.push_back(0);
ll lim = 1;
for(int bit=0;bit<nop;bit++)
{
for(int i=0;i<n;i++)
{
if(s[i]<lim) add[bit][0][i] = s[i], jump[bit][0][i] = w[i];
else add[bit][0][i] = p[i], jump[bit][0][i] = l[i];
diff[bit][0][i] = add[bit][0][i]-s[i];
mx[bit][0][i] = s[i];
}
add[bit][0][n] = 0, jump[bit][0][n] = n, diff[bit][0][n] = 0, mx[bit][0][n] = 0;
for(int i=1;i<noa;i++)
{
for(int j=0;j<=n;j++)
{
ll nxt = jump[bit][i-1][j];
add[bit][i][j] = add[bit][i-1][j] + add[bit][i-1][nxt];
diff[bit][i][j] = max(diff[bit][i-1][j], add[bit][i-1][j]+diff[bit][i-1][nxt]);
mx[bit][i][j] = max(mx[bit][i-1][j],mx[bit][i-1][nxt]);
jump[bit][i][j] = jump[bit][i-1][nxt];
}
}
lim *= base;
}
return;
}
ll simulate(int x, int z)
{
ll pos = x;
ll str = z;
ll lim = 1;
ll phase = 0;
while(pos!=N && phase<nop)
{
for(int i=noa-1;i>=0;i--)
{
//next stage
if(str+diff[phase][i][pos]>=0 && mx[phase][i][pos]>=lim) continue;
str += add[phase][i][pos];
pos = jump[phase][i][pos];
}
if(pos==N) continue;
if(str>=S[pos]) str += S[pos], pos = W[pos];
else str += P[pos], pos = L[pos];
phase++;
lim *= base;
}
return str;
}