Submission #347443

#	Time	Username	Problem	Language	Result	Execution time	Memory
347443		milleniumEeee	The Big Prize (IOI17_prize)	C++17	90 / 100	90 ms	640 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
 
int find_best(int n) {
  if (n == 1) {
    return 0;
  }
  int S = sqrt(n);
  if (S * S < n) {
    S++;
  }
  int pos = 0;
  int big = 0;
  for (int i = 0; i <= S * 2; i++) {
    vector <int> res = ask(i);
    if (res[0] == 0 && res[1] == 0) {
      return i;
    }
    big = max(big, res[0] + res[1]);
  }
  pos = S + 1;
  while(1) {
    vector <int> pres = ask(pos);
    if (pres[0] == 0 && pres[1] == 0) {
      return pos;
    }
    if (pres[0] + pres[1] == big) {
      int l = pos, r = n;
      while(r - l > 1) {
        int mid = (l + r) >> 1; 
        vector <int> mres = ask(mid);
        if (pres[0] == mres[0] && pres[1] == mres[1]) {
          l = mid;
        } else {
          r = mid;
        }
      }
      pos = l + 1;
    } else {
      pos++;
    }
  }
}

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