제출 #347447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347447		milleniumEeee	The Big Prize (IOI17_prize)	C++17	20 / 100	87 ms	492 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef vector<int> vi;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int get_rand() {
  long long x = rnd();
  if (x < 0) {
    x = -x;
  }
  x %= (int)1e9;
  return x;
}

int gen(int l, int r) {
  return l + (get_rand() % (r - l + 1));
}

int f(int n) {
  int p = gen(0, n - 1);
  vector <int> vec = ask(p);
  return vec[0] + vec[1];
} 
 
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;
  if (n < 1e5) {
    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;    
  } else {
    for (int i = 1; i <= 10; i++) {
      big = max(big, f(n));      
    }
    pos = 0;
  }
  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: 0 / 80