oj.uz

Submission #131293

# Submission time Handle Problem Language Result Execution time Memory
131293 2019-07-17T01:27:53 Z dragonslayerit Hotter Colder (IOI10_hottercolder) C++14
92 / 100
 976 ms 8204 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) %d\n",1,N,l,r,last,g);
  assert(last!=-1);
  if(last==g){
    if(g==1) g++;
    else if(g==N) g--;
    else if(rand()%2){
      g++;
    }else{
      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+int((r-l)*0.4));
  }
  while((r==N)&&(l<r)){
    Refine(r-int((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 32 ms 1272 KB Output is correct

Subtask #2
25.0 / 25.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
17.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 976 ms 8204 KB Output is partially correct - alpha = 0.666666666667