Submission #172358

#	Time	Username	Problem	Language	Result	Execution time	Memory
172358		AlexLuchianov	커다란 상품 (IOI17_prize)	C++14	20 / 100	92 ms	424 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 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){
  ///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, 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);
	special = 100;

  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(MIN(special + 1, n - 1), n - 1, 0, 0);
  assert(0 <= diamond);
	return diamond;
}

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