# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1017278 | 2024-07-09T07:08:38 Z | overwatch9 | The Big Prize (IOI17_prize) | C++17 | 0 ms | 0 KB |
#include "prize.h" #include <bits/stdc++.h> using namespace std; int N; vector <int> nums; vector <int> ask(int i) { vector <int> ans(2, 0); for (int j = 0; j < i; j++) { if (nums[j] > nums[i]) ans[0]++; } for (int j = i+1; j < N; j++) { if (nums[j] > nums[i]) ans[1]++; } return ans; } int find_best(int n) { int lo = 0, hi = n-1; cout << n << '\n'; while (lo <= hi) { int mid = (lo + hi) / 2; auto res = ask(mid); // cout << "GUESS: " << mid << '\n'; // cout << "RESULT: " << res[0] << ' ' << res[1] << '\n'; if (res[0] + res[1] == 0) return mid; if (res[0] > res[1]) hi = mid-1; else lo = mid+1; } return lo; } // int main() { // cin >> N; // nums.resize(N+1); // for (int i = 0; i < N; i++) // cin >> nums[i]; // find_best(N); // }