Submission #94472

#	Time	Username	Problem	Language	Result	Execution time	Memory
94472		wxh010910	The Big Prize (IOI17_prize)	C++17	100 / 100	50 ms	2216 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;

int find_best(int n) {
  vector<pair<int, int>> ans(n);
  unordered_map<int, set<int>> s;
  function<int(int, int)> solve = [&](int l, int r) {
    if (l > r) {
      return -1;
    }
    int mid = l + r >> 1;
    vector<int> a = ask(mid);
    ans[mid] = make_pair(a[0], a[1]);
    int sum = ans[mid].first + ans[mid].second;
    if (!sum) {
      return mid;
    }
    auto it = s[sum].insert(mid).first;
    if (it == s[sum].begin() || ans[*prev(it)].first != ans[mid].first) {
      int res = solve(l, mid - 1);
      if (res != -1) {
        return res;
      }
    }
    if (it == --s[sum].end() || ans[*next(it)].second != ans[mid].second) {
      int res = solve(mid + 1, r);
      if (res != -1) {
        return res;
      }
    }
    return -1;
  };
  return solve(0, n - 1);
}

Compilation message (stderr)

prize.cpp: In lambda function:
prize.cpp:13:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80