Submission #172354

#	Time	Username	Problem	Language	Result	Execution time	Memory
172354		AlexLuchianov	The Big Prize (IOI17_prize)	C++14	97.68 / 100	73 ms	5256 KiB

prize

#include "prize.h"
#include <cmath>
#include <iostream>
#include <cassert>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;

int identity = 0, diamond = -1;

int queries = 0;

std::vector<int> already[1 + nmax];

std::vector<int> realask(int x){
  if(already[x].size() == 0) {
    std::vector<int> sol = ask(x);
    already[x] = sol;
    if(sol[0] + sol[1] == 0)
      diamond = x;
  }
  return already[x];
}

void solve(int from, int to, int left, int right){

  ///invalid interval
  if(to < from) {
    //std::cout << "Invalid\n";
    return ;
  }
  ///no special element here :(
  if(identity == left + right) {
    //std::cout << "Muggle\n";
    return ;
  }

  ///diamond was already found
  if(0 <= diamond) {
    //std::cout << "Already\n";
    return ;
  }

  int mid = (from + to) / 2;
  std::vector<int> sol = realask(mid);
  if(sol[0] + sol[1] == identity){
    solve(from, mid - 1, left, sol[1]);
    solve(mid + 1, to, sol[0], right);
  } else {
    int mid2 = mid + 1;
    while(mid2 <= to){
      sol = realask(mid2);
      if(sol[0] + sol[1] == identity) {
        solve(mid2 + 1, to, sol[0], right);
        break;
      }
      mid2++;
    }
    mid2 = mid - 1;
    while(from <= mid2){
      sol = realask(mid2);
      if(sol[0] + sol[1] == identity){
        solve(from, mid2 - 1, left, sol[1]);
        break;
      }
      mid2--;
    }
  }
}

int find_best(int n) {
	int special = 0;
	int n2 = sqrt(n);
	while(1 <= n2){
    special += n2;
    n2 = sqrt(n2 - 1);
	}
	//special = 0;
	//std::cout << n << " " << special << '\n';
	assert(special <= 800);

  for(int i = 0;i < MIN(special + 1, n - 1); i++){
    std::vector<int> sol = realask(i);
    identity = MAX(identity, sol[0] + sol[1]);
  }
  solve(0, n - 1, 0, 0);
  assert(0 <= diamond);
  assert(queries <= 10000);
	return diamond;
}

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