Submission #1260016

#TimeUsernameProblemLanguageResultExecution timeMemory
1260016Faggi커다란 상품 (IOI17_prize)C++20
100 / 100
15 ms916 KiB
#include <bits/stdc++.h> #define ll long long #define sz(x) int(x.size()) #define forn(i, n) for (i = 0; i < n; i++) #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair #define fr first #define se second using namespace std; vector<int> ask(int i); const int MAXM = 450; map<ll, vector<int>> memo; ll ans = 0; int N, ma; bool enc = 0; vector<int> cons(ll x) { if (enc) return {N, N}; auto it = memo.find(x); if (it == memo.end()) memo[x] = ask(x); if (memo[x][0] + memo[x][1] == 0) { enc = 1; ans = x; } return memo[x]; } int sum(ll x) { vector<int> ret = cons(x); return ret[1] + ret[0]; } bool lolip(ll x) { vector<int> q = cons(x); ll cant = q[0] + q[1]; return cant >= ma; } void solve(ll l, ll r, ll il, ll ir) { if (il == ir || enc) return; if (l == r) { cons(l); return; } ll mid = (l + r) / 2; while (!enc && mid >= l && !lolip(mid)) mid--; if (enc) return; if (mid >= l) { solve(l, mid, il, cons(mid)[0]); if (enc) return; solve((l + r) / 2 + 1, r, cons(mid)[0] + abs(((l + r) / 2) - mid), ir); } } int find_best(int n) { ll a = 0, i, b = n - 1; for (i = 0; i < min(MAXM, n); i++) { ma = max(ma, sum(i)); ll x = (ma * ma + 1); if (x * x + 1LL > n) break; } N = n; for (i = 0; i < MAXM; i++) { if (enc || lolip(i)) { a = i; break; } } for (i = n - 1; i >= n - MAXM; i--) { if (enc || lolip(i)) { b = i; break; } } solve(a, b, cons(a)[0], cons(b)[0]); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...