Submission #1056508

#TimeUsernameProblemLanguageResultExecution timeMemory
1056508vnm06Dungeons Game (IOI21_dungeons)C++17
37 / 100
772 ms252712 KiB
#include "dungeons.h" #include<bits/stdc++.h> #include <vector> using namespace std; int N; vector<int> S, P, W, L; int ans[3000000][4], br=0; vector<int> grL[400005], grW[400005]; map<pair<int, int>, int > mp[400005]; void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) { N=n; S=s; P=p; W=w; L=l; for(int i=0; i<n; i++) { grL[L[i]].push_back(i); grW[W[i]].push_back(i); } ans[0][0]=n; ans[0][1]=0; ans[0][2]=2e8; ans[0][3]=0; br=1; for(int i=0; i<br; i++) { int v=ans[i][0], be=ans[i][1], en=ans[i][2], dob=ans[i][3]; int brL=grL[v].size(); for(int j=0; j<brL; j++) { int nv=grL[v][j], nbe=be-P[nv], nen=en-P[nv], ndob=dob+P[nv]; if(nbe<0) nbe=0; if(nen>=S[nv]) nen=S[nv]-1; if(nen>=nbe) { ans[br][0]=nv; ans[br][1]=nbe; ans[br][2]=nen; ans[br][3]=ndob; br++; } } int brW=grW[v].size(); for(int j=0; j<brW; j++) { int nv=grW[v][j], nbe=be-S[nv], nen=en-S[nv], ndob=dob+S[nv]; if(nbe<S[nv]) nbe=S[nv]; if(nen>=nbe) { ans[br][0]=nv; ans[br][1]=nbe; ans[br][2]=nen; ans[br][3]=ndob; br++; } } } for(int i=0; i<br; i++) { int v=ans[i][0], be=ans[i][1], en=ans[i][2], dob=ans[i][3]; mp[v][{be, en}]=dob; } } long long simulate(int x, int z) { map<pair<int, int>, int >::iterator it=mp[x].lower_bound({z, 1e9}); it--; return z+(*it).second; }
#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...