oj.uz

Submission #131302

# Submission time Handle Problem Language Result Execution time Memory
131302 2019-07-17T02:53:54 Z dragonslayerit Hotter Colder (IOI10_hottercolder) C++14
97 / 100
 3424 ms 35292 KB 
#include "grader.h"
#include <cstdio>
#include <cassert>
#include <algorithm>

const int SMALL=85;

char cost[SMALL+2][SMALL+2][SMALL+2][SMALL+2];//l,r,x

void Brute(int N){
  if(cost[N][1][N][1]) return;
  for(int l=0;l<=N;l++){
    for(int r=0;r<=N;r++){
      for(int x=1;x<=N;x++){
	cost[N][l][r][x]=50;
      }
    }
  }
  for(int l=1;l<=N;l++){
    for(int x=1;x<=N;x++){
      cost[N][l][l][x]=0;
    }
  }
  //Assuming OPT will never make a guess without reducing interval
  //Seems to be true from experimentation
  for(int l=N;l>0;l--){
    for(int r=l;r<=N;r++){
      for(int x=1;x<=N;x++){
	int k=-1;
	for(int y=1;y<=N;y++){
	  if(y==x) continue;
	  int ml=(x+y-1)/2;
	  int mr=(x+y)/2+1;
	  int v=1+std::max(cost[N][l][std::min(r,ml)][y],cost[N][std::max(l,mr)][r][y]);
	  if(cost[N][l][r][x]>v){
	    cost[N][l][r][x]=v;
	    k=y;
	  }
	}
	//printf("cost[%d][%d][%d]=%d (%d)\n",l,r,x,cost[N][l][r][x],k);
      }
    }
  }
}



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);
  g=std::max(1,std::min(N,g));
  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);
  ::N=N;
  l=1,r=N;
  if(N<=SMALL){
    Brute(N);
    Guess(last=std::min_element(cost[N][1][N]+1,cost[N][1][N]+N+1)-cost[N][1][N]);
    while(l<r){
      int x=last;
      for(int y=1;y<=N;y++){
	int ml=(x+y-1)/2;
	int mr=(x+y)/2+1;
	if(cost[N][l][r][x]==1+std::max(cost[N][l][std::min(r,ml)][y],cost[N][std::max(l,mr)][r][y])){
	  Refine(y);
	  break;
	}
      }
    }
    return l;
  }
  Guess(last=(l+r)/2);
  Refine(last+1);
  int p1=0,p2=0;
  while(l==1&&(l<r)){
    Refine(l+int((r-l)*0.367));
    p1++;
  }
  while((r==N)&&(l<r)){
    Refine(r-int((r-l)*0.367));
    p1++;
  }
  while(l<r){
    Refine(l+r-last);
    p2++;
  }
  //printf("HC(%d,%d): %d+%d\n",N,l,p1,p2);
  return l;
}

Compilation message

hottercolder.cpp: In function 'void Brute(int)':
hottercolder.cpp:29:6: warning: variable 'k' set but not used [-Wunused-but-set-variable]
  int k=-1;
      ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2633 ms 28280 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2652 ms 28452 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2604 ms 28452 KB Output is correct

Subtask #4
22.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 3424 ms 35292 KB Output is partially correct - alpha = 0.875000000000