Submission #442337

#TimeUsernameProblemLanguageResultExecution timeMemory
442337SorahISADungeons Game (IOI21_dungeons)C++17
13 / 100
161 ms37332 KiB
#include "dungeons.h" #pragma GCC optimize("Ofast", "unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long // #define double long double using pii = pair<int, int>; template<typename T> using Prior = std::priority_queue<T>; template<typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>; #define X first #define Y second #define eb emplace_back #define pb pop_back #define pf pop_front #define ALL(x) begin(x), end(x) #define RALL(x) rbegin(x), rend(x) namespace { mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // const int maxn = 4E5 + 5; const int maxn = 5E4 + 5; // const int w_lgmx = 19 + 1; const int w_lgmx = 16 + 1; const int l_lgmx = 24 + 1; int N; vector<int> S, P, W, L; int win_anc[w_lgmx][maxn], win_sum[w_lgmx][maxn], win_val[w_lgmx][maxn]; int los_anc[l_lgmx][maxn], los_sum[l_lgmx][maxn]; } /// end of namespace void init(int32_t _N, vector<int32_t> _S, vector<int32_t> _P, vector<int32_t> _W, vector<int32_t> _L) { N = _N; for (auto &x : _S) S.eb(x); S.eb(0); for (auto &x : _P) P.eb(x); P.eb(0); for (auto &x : _W) W.eb(x); W.eb(N); for (auto &x : _L) L.eb(x); L.eb(N); memset(win_anc, 0x00, sizeof(win_anc)); memset(win_sum, 0x00, sizeof(win_sum)); // memset(win_val, 0x00, sizeof(win_val)); memset(los_anc, 0x00, sizeof(los_anc)); memset(los_sum, 0x00, sizeof(los_sum)); for (int i = 0; i < N; ++i) { win_anc[0][i] = W[i]; win_sum[0][i] = S[i]; // win_val[0][i] = S[i]; los_anc[0][i] = L[i]; los_sum[0][i] = P[i]; } win_anc[0][N] = los_anc[0][N] = N; for (int lay = 1; lay < w_lgmx; ++lay) { for (int i = 0; i <= N; ++i) { int win_par = win_anc[lay-1][i]; win_anc[lay][i] = win_anc[lay-1][win_par]; win_sum[lay][i] = win_sum[lay-1][i] + win_sum[lay-1][win_par]; // win_val[lay][i] = max(win_val[lay-1][i], win_val[lay-1][win_par]); } } for (int lay = 1; lay < l_lgmx; ++lay) { for (int i = 0; i <= N; ++i) { int los_par = los_anc[lay-1][i]; los_anc[lay][i] = los_anc[lay-1][los_par]; los_sum[lay][i] = los_sum[lay-1][i] + los_sum[lay-1][los_par]; } } } int simulate(int32_t now, int32_t _Z) { /// s[i] = s[j] /// int Z = _Z; if (Z >= S[0]) return Z + win_sum[w_lgmx-1][now]; for (int lay = l_lgmx-1; lay >= 0 and now != N; --lay) { if (Z + los_sum[lay][now] < S[now]) { Z += los_sum[lay][now]; now = los_anc[lay][now]; } // cerr << "(Z, now): " << Z << "," << now << "\n"; } Z += P[now], now = L[now]; return Z + win_sum[w_lgmx-1][now]; }

Compilation message (stderr)

dungeons.cpp: In function 'void init(int32_t, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:42:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   42 |     for (auto &x : _S) S.eb(x); S.eb(0);
      |     ^~~
dungeons.cpp:42:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   42 |     for (auto &x : _S) S.eb(x); S.eb(0);
      |                                 ^
dungeons.cpp:43:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |     for (auto &x : _P) P.eb(x); P.eb(0);
      |     ^~~
dungeons.cpp:43:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |     for (auto &x : _P) P.eb(x); P.eb(0);
      |                                 ^
dungeons.cpp:44:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   44 |     for (auto &x : _W) W.eb(x); W.eb(N);
      |     ^~~
dungeons.cpp:44:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   44 |     for (auto &x : _W) W.eb(x); W.eb(N);
      |                                 ^
dungeons.cpp:45:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   45 |     for (auto &x : _L) L.eb(x); L.eb(N);
      |     ^~~
dungeons.cpp:45:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   45 |     for (auto &x : _L) L.eb(x); L.eb(N);
      |                                 ^
dungeons.cpp: At global scope:
dungeons.cpp:35:51: warning: '{anonymous}::win_val' defined but not used [-Wunused-variable]
   35 | int win_anc[w_lgmx][maxn], win_sum[w_lgmx][maxn], win_val[w_lgmx][maxn];
      |                                                   ^~~~~~~
#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...