Submission #133374

#	Time	Username	Problem	Language	Result	Execution time	Memory
133374		IOrtroiii	The Big Prize (IOI17_prize)	C++14	100 / 100	71 ms	10792 KiB

prize

#include <bits/stdc++.h>

#include "prize.h"

using namespace std;

set<int> s[200200];
int ans[200200];

int solve(int l, int r) {
   if (l > r) {
      return -1;
   }
   int md = (l + r) >> 1;
   vector<int> a = ask(md);
   ans[md] = a[0];
   int all = a[0] + a[1];
   if (all == 0) {
      return md;
   }
   auto it = s[all].insert(md).first;
   if (it == s[all].begin() || ans[*prev(it)] != ans[md]) {
      int cur = solve(l, md - 1);
      if (~cur) return cur;
   }
   if (it == --s[all].end() || ans[*next(it)] != ans[md]) {
      int cur = solve(md + 1, r);
      if (~cur) return cur;
   }
   return -1;
}

int find_best(int n) {
   return solve(0, n - 1);
}

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