Submission #1256224

#TimeUsernameProblemLanguageResultExecution timeMemory
1256224biankThe Big Prize (IOI17_prize)C++20
100 / 100
14 ms916 KiB
#include <bits/stdc++.h> using namespace std; #define forn(i, n) for (int i = 0; i < int(n); i++) #define forsn(i, s, n) for (int i = int(s); i < int(n); i++) #define dforn(i, n) for (int i = int(n) - 1; i >= 0; i--) #define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--) #define all(x) begin(x), end(x) #define sz(x) (int)(x.size()) using vi = vector<int>; using ll = long long; #define pb push_back #define eb emplace_back #define fst first #define snd second vi ask(int i); map<int, vi> memo; bool found = false; int maxi; vi query(int i) { if (found) return {maxi, maxi}; if (memo.count(i)) return memo[i]; return memo[i] = ask(i); } int querySum(int i) { vi a = query(i); if (a[0] + a[1] == 0) found = true; return a[0] + a[1]; } const int K = 450; void solve(int lo, int hi, int s, int e) { if (s == e || found) return; if (lo == hi) { query(lo); return; } int mid = (lo + hi) / 2; while (!found && mid >= lo && querySum(mid) < maxi) mid--; if (mid >= lo) { solve(lo, mid, s, query(mid)[0]); solve((lo + hi) / 2 + 1, hi, query(mid)[0] + (lo + hi) / 2 - mid, e); } else { solve((lo + hi) / 2 + 1, hi, s + mid - lo + 1, e); } } int find_best(int n) { maxi = 0; forn(i, min(K, n)) { maxi = max(maxi, querySum(i)); if ((maxi * maxi + 1LL) * (maxi * maxi + 1LL) + 1LL > n) break; if (found) break; } int lo = 0, hi = n - 1; while (!found && querySum(lo) != maxi) lo++; while (!found && querySum(hi) != maxi) hi--; solve(lo, hi, query(lo)[0], query(hi)[0]); for (auto [i, a] : memo) { if (a[0] + a[1] == 0) return i; } assert(false); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...