제출 #172344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172344		AlexLuchianov	The Big Prize (IOI17_prize)	C++14	0 / 100	7 ms	424 KiB

prize

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

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

int identity = 0, diamond = -1;

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

void solve(int from, int to, int left, int right){
  std::cout << from << " " << to << " " << left << " " << right << '\n';

  ///invalid interval
  if(to < from)
    return ;
  ///no special element here :(
  if(identity == left + right)
    return ;

  ///diamond was already found
  if(0 <= diamond)
    return ;

  int mid = (from + to) / 2;
  std::vector<int> sol = realask(mid);
  if(sol[0] + sol[1] == identity){
    solve(from, mid - 1, left, right + sol[1]);
    solve(mid + 1, to, left + sol[0], right);
  } else {
    int mid2 = mid + 1;
    while(mid2 <= to){
      sol = realask(mid2);
      if(sol[0] + sol[1] == identity) {
        solve(mid2 + 1, to, left + 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, right + 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';
  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);
	return diamond;
}

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