Submission #829436

#TimeUsernameProblemLanguageResultExecution timeMemory
829436ymmDungeons Game (IOI21_dungeons)C++17
63 / 100
1574 ms843680 KiB
#include "dungeons.h" #include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (r); ++x) #define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x) typedef long long ll; using namespace std; const int N = 50'010; const int lg = 24; const int S = 12; int nxt[S][lg][N]; ll add[S][lg][N]; ll mn[S][lg][N]; ll mx[S][lg][N]; vector<int> s, p, w, l; vector<int> cmp, scmp; int n; 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; Loop (i,0,S-1) cmp.push_back(64<<(2*i)); Loop (i,0,n) scmp.push_back(lower_bound(cmp.begin(), cmp.end(), s[i]) - cmp.begin()); Loop (k,0,cmp.size()+1) { Loop (i,0,n) { nxt[k][0][i] = (scmp[i] < k? w[i]: l[i]); add[k][0][i] = (scmp[i] < k? s[i]: p[i]); mn[k][0][i] = (scmp[i] < k? s[i]: 0); mx[k][0][i] = (scmp[i] < k? (ll)1e18: s[i]); } nxt[k][0][n] = n; Loop (j,0,lg-1) Loop (i,0,n+1) { nxt[k][j+1][i] = nxt[k][j][nxt[k][j][i]]; add[k][j+1][i] = add[k][j][i] + add[k][j][nxt[k][j][i]]; mn[k][j+1][i] = max(mn[k][j][i], mn[k][j][nxt[k][j][i]] - add[k][j][i]); mx[k][j+1][i] = min(mx[k][j][i], mx[k][j][nxt[k][j][i]] - add[k][j][i]); } } } long long simulate(int x, int z) { ll val = z; int k = 0; while (val < 64 && x != n) { if (val < s[x]) { val += p[x]; x = l[x]; } else { val += s[x]; x = w[x]; } } for (;;) { LoopR (i,0,lg) { if (mn[k][i][x] <= val && val < mx[k][i][x]) { val += add[k][i][x]; x = nxt[k][i][x]; } } if (x == n) break; assert(val >= s[x]); if (val < s[x]) { val += p[x]; x = l[x]; } else { val += s[x]; x = w[x]; } k = upper_bound(cmp.begin(), cmp.end(), val) - cmp.begin(); } return val; }

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
dungeons.cpp:29:2: note: in expansion of macro 'Loop'
   29 |  Loop (k,0,cmp.size()+1) {
      |  ^~~~
#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...