Submission #294729

#	Time	Username	Problem	Language	Result	Execution time	Memory
294729		ASDF123	The Big Prize (IOI17_prize)	C++14	90 / 100	94 ms	384 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++;
    }
  }
}

//#include <bits/stdc++.h>
//using namespace std;

//signed main() { 
  //cout << log2(200000) << endl;
  
  //int cnt = 190000;
  //while (cnt > 1) {
    //cout << cnt << endl;
    //cnt = sqrt(cnt);
  //}
  //double ans = 190000 * sqrt(190000) 
//}

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