제출 #246848

#제출 시각아이디문제언어결과실행 시간메모리
246848hhh07커다란 상품 (IOI17_prize)C++14
0 / 100
17 ms9984 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<vi> res(n, vi()); 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, 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; } } i = beg + 1; } else i++; } return i; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...