oj.uz

Submission #131291

# Submission time Handle Problem Language Result Execution time Memory
131291 2019-07-17T01:07:50 Z dragonslayerit Hotter Colder (IOI10_hottercolder) C++14
87 / 100
 830 ms 8184 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||r==N)&&(l<r)){
    Refine((l+r)/2);
  }
  while(l<r){
    Refine(l+r-last);
  }
  return l;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
12.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 830 ms 8184 KB Output is partially correct - alpha = 0.500000000000