제출 #247009

#제출 시각아이디문제언어결과실행 시간메모리
247009hhh07커다란 상품 (IOI17_prize)C++14
0 / 100
17 ms10128 KiB
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <utility> #include <set> #include <cmath> #include <cstring> #include "prize.h" using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<ll, ll> ii; vector<vi> res(2e5 + 1, vi()); int find_best(int n){ int maxi = 0; for (int i = 0; i < min(500, n); i++){ res[i] = ask(i); if (res[i][0] + res[i][1] == 0) return i; maxi = max(maxi, res[i][0] + res[i][1]); } int i = 500; while(i < n){ if (res[i].size() == 0) res[i] = ask(i); if (res[i][0] + res[i][1] == 0) return i; if (res[i][0] + res[i][1] == maxi){ int beg = i + 1, end = n - 1; while(beg < end){ int mid = (beg + end)/2; if (res[i].size() == 0) res[mid] = ask(mid); if (res[mid][0] + res[mid][1] == 0) return mid; if (res[mid][0] + res[mid][1] < maxi) end = mid; else{ if (res[i][1] - res[mid][1] > 0) end = mid - 1; else beg = mid + 1; } } if (res[beg].size() == 0) res[beg] = ask(beg); if (res[beg][0] + res[beg][1] == 0) return beg; i = beg + 1; } else i++; } return i; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...