제출 #131292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131292		dragonslayerit	Hotter Colder (IOI10_hottercolder)	C++14	90 / 100	986 ms	8324 KiB

hottercolder

#include "grader.h"
#include <cstdio>
#include <cassert>
#include <algorithm>

int N;
int l,r;
int last;


void Refine(int g){
  //printf("[%d,%d]: [%d,%d] (%d)\n",1,N,l,r,last);
  assert(last!=-1);
  if(last==g){
    g++;
  }
  assert(g>=1&&g<=N);
  int res=Guess(g);
  //printf("Guess(%d)=>%d\n",g,res);
  if(res==0){
    l=r=(last+g)/2;
    return;
  }
  int ml=(last+g-1)/2;
  int mr=(last+g)/2+1;
  if((g<last)^(res<0)){
    r=std::min(r,ml);
  }else{
    l=std::max(l,mr);
  }
  last=g;
}
     
int HC(int N){
  //printf("HC(%d)\n",N);
  if(N==1) return 1;
  ::N=N;
  l=1,r=N;
  Guess(last=(l+r)/2);
  Refine(last+1);
  while(l==1&&(l<r)){
    Refine(l+(r-l)*0.4);
  }
  while((r==N)&&(l<r)){
    Refine(r-(r-l)*0.4);
  }
  while(l<r){
    Refine(l+r-last);
  }
  return l;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 15 / 25