Submission #921277

#TimeUsernameProblemLanguageResultExecution timeMemory
921277byunjaewooDungeons Game (IOI21_dungeons)C++17
11 / 100
1427 ms2097152 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; using ll=long long; const int Nmax=400010; int N, S[Nmax], P[Nmax], W[Nmax], L[Nmax]; vector<int> nxt[25][Nmax], mx[25][Nmax], sum[25][Nmax]; void init(int n, std::vector<int> S_, std::vector<int> P_, std::vector<int> W_, std::vector<int> L_) { N=n; for(int i=0; i<N; i++) S[i]=S_[i], P[i]=P_[i], W[i]=W_[i], L[i]=L_[i]; for(int i=0; i<25; i++) for(int j=0; j<=N; j++) nxt[i][j].resize(i), mx[i][j].resize(i), sum[i][j].resize(i); for(int i=1; i<25; i++) { for(int j=0; j<N; j++) { if(S[j]>=(1<<(i+1))) nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=(1<<(i+1))-1-P[j]; else if(S[j]<=(1<<i)) nxt[i][j][0]=W[j], sum[i][j][0]=S[j], mx[i][j][0]=(1<<(i+1))-1-S[j]; else nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=min(S[j]-1, (1<<(i+1))-1-P[j]); } nxt[i][N][0]=N, sum[i][N][0]=0, mx[i][N][0]=(1<<(i+1))-1; for(int j=1; j<i; j++) for(int k=0; k<=N; k++) { nxt[i][k][j]=nxt[i][nxt[i][k][j-1]][j-1]; sum[i][k][j]=sum[i][k][j-1]+sum[i][nxt[i][k][j-1]][j-1]; mx[i][k][j]=min(mx[i][k][j-1], mx[i][nxt[i][k][j-1]][j-1]-sum[i][k][j-1]); } } for(int j=0; j<25; j++) for(int k=0; k<=N; k++) mx[24][k][j]=INT_MAX; } long long simulate(int x, int z) { int k=x; ll v=z; for(int i=0; i<25; i++) { int kk=k; ll vv=v; for(int j=i-1; j>=0; j--) if(vv<=mx[i][kk][j]) { vv+=sum[i][kk][j], kk=nxt[i][kk][j]; if(kk==N) break; } if(kk==N) { for(int j=i-1; j>=0; j--) if(nxt[i][k][j]!=N) v+=sum[i][k][j], k=nxt[i][k][j]; if(k!=N) v+=sum[i][k][0], k=nxt[i][k][0]; return v; } if(vv<(1<<(i+1))) { if(vv>=S[kk]) vv+=S[kk], kk=W[kk]; else vv+=P[kk], kk=L[kk]; } k=kk, v=vv; } }

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...