제출 #246860

#제출 시각아이디문제언어결과실행 시간메모리
246860hhh07커다란 상품 (IOI17_prize)C++14
90 / 100
101 ms512 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; int find_best(int n){ vector<int> res; int maxi = 0; for (int i = 0; i < min(500, n); i++){ res = ask(i); if (res[0] + res[1] == 0) return i; maxi = max(maxi, res[0] + res[1]); } int i = 500; while(i < n){ res = ask(i); if (res[0] + res[1] == 0) return i; if (res[0] + res[1] == maxi){ int beg = i + 1, end = n - 1; while(beg < end){ int mid = (beg + end)/2; vi t; t = ask(mid); if (t[0] + t[1] == 0) return mid; if (t[0] + t[1] < maxi) end = mid; else{ if (res[1] - t[1] > 0) end = mid - 1; else beg = mid + 1; } } res = ask(beg); if (res[0] + res[1] == 0) return beg; i = beg + 1; } else i++; } return i; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...