제출 #574548

#제출 시각아이디문제언어결과실행 시간메모리
574548valerikk커다란 상품 (IOI17_prize)C++17
90 / 100
122 ms11276 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; mt19937 rnd(239); namespace { int mx_cnt; } vector<vector<int>> mem; vector<int> mask(int i) { return mem[i] == vector<int>{-1, -1} ? mem[i] = ask(i) : mem[i]; } int solve(int l, int r) { if (l > r) return -1; if (l == r) { auto a = mask(l); if (a[0] + a[1] == 0) return l; return -1; } auto al = mask(l); auto ar = mask(r); if (al[0] + al[1] == 0) return l; if (ar[0] + ar[1] == 0) return r; if (al[0] + al[1] == mx_cnt && ar[0] + ar[1] == mx_cnt && al[0] == ar[0]) return -1; int m = (l + r) / 2; int res; if (rnd() & 1) { res = solve(l, m); if (res == -1) res = solve(m + 1, r); } else { res = solve(m + 1, r); if (res == -1) res = solve(l, m); } return res; } int find_best(int n) { mem = vector<vector<int>>(n, vector<int>{-1, -1}); mx_cnt = 0; for (int i = 0; i < min(n, 500); ++i) { auto a = mask(i); if (a[0] + a[1] == 0) return i; mx_cnt = max(mx_cnt, a[0] + a[1]); } return solve(0, n - 1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...