제출 #813672

#제출 시각아이디문제언어결과실행 시간메모리
813672skittles1412던전 (IOI21_dungeons)C++17
0 / 100
1577 ms2097152 KiB
#include "bits/extc++.h" using namespace std; template <typename T, typename... U> void dbgh(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; } #ifdef DEBUG #define dbg(...) \ cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \ dbgh(__VA_ARGS__) #else #define dbg(...) #define cerr \ if (false) \ cerr #endif using ll = long long; #define endl "\n" #define long int64_t #define sz(x) int(std::size(x)) struct Dungeon { int s, p, w, l; }; struct DS1 { struct Lift { long mn_esc; int win_d, lose_d; long add, win_add; }; static constexpr int LOGN = 30; int n, kv; vector<Dungeon> arr; vector<Lift> lift[LOGN]; DS1() {} DS1(int kv, const vector<Dungeon>& arr) : n(sz(arr)), kv(kv), arr(arr) { for (auto& a : lift) { a.resize(n + 1); } for (int i = 0; i < n; i++) { auto& [s, p, w, l] = arr[i]; if (__lg(s) < kv) { lift[0][i] = {w == n ? 0 : (long(1) << (kv + 1)) - s, w, w, s, s}; continue; } else if (__lg(s) > kv) { lift[0][i] = {l == n ? 0 : (long(1) << (kv + 1)) - p, l, l, p, p}; continue; } lift[0][i] = {l == n ? 0 : min(long(s), (long(1) << (kv + 1)) - p), w, l, p, s}; } lift[0][n] = {0, n, n, 0, 0}; for (int it = 1; it < LOGN; it++) { for (int i = 0; i <= n; i++) { auto& ql = lift[it - 1][i]; auto& qr = lift[it - 1][ql.lose_d]; lift[it][i] = {max(long(0), min(ql.mn_esc, qr.mn_esc - ql.add)), qr.win_d, qr.lose_d, ql.add + qr.add, ql.add + qr.win_add}; } } } void advance(int& u, long& w) { if (u == n || __lg(w) > kv) { return; } assert(__lg(w) == kv); for (int it = LOGN - 1; it >= 0; it--) { auto& cq = lift[it][u]; if (w >= cq.mn_esc) { continue; } u = cq.lose_d; w += cq.add; dbg(it, u, w); } dbg(kv, u, w); assert(u != n && __lg(w) == kv); dbg(u, arr[u].s, arr[u].p); if (w >= arr[u].s) { w += arr[u].s; u = arr[u].w; } else { w += arr[u].p; u = arr[u].l; } // auto& cq = lift[0][u]; // u = cq.win_d; // w += cq.win_add; dbg(u, w); assert(u == n || __lg(w) > kv); } }; struct Solver { static constexpr int LOGN = 60; int n; DS1 lift[LOGN]; Solver() {} Solver(const vector<Dungeon>& arr) : n(sz(arr)) { for (int i = 0; i < LOGN; i++) { lift[i] = DS1(i, arr); } } long query(int u, long kv) { for (auto& a : lift) { a.advance(u, kv); } assert(u == n); return kv; } } solver; void init(int n, vector<int> arr_s, vector<int> arr_p, vector<int> arr_w, vector<int> arr_l) { vector<Dungeon> arr; for (int i = 0; i < n; i++) { arr.push_back({arr_s[i], arr_p[i], arr_w[i], arr_l[i]}); } solver = Solver(arr); } ll simulate(int u, int kv) { return solver.query(u, kv); }
#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...