oj.uz

Submission #131292

# Submission time Handle Problem Language Result Execution time Memory
131292 2019-07-17T01:14:59 Z dragonslayerit Hotter Colder (IOI10_hottercolder) C++14
90 / 100
 986 ms 8324 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1372 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1272 KB Output is correct

Subtask #4
15.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 986 ms 8324 KB Output is partially correct - alpha = 0.600000000000