Submission #319674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
319674	2020-11-06T06:05:00 Z	seedkin	Hotter Colder (IOI10_hottercolder)	C	80 / 100	673 ms	9060 KB

hottercolder

#include "grader.h"
#include <stdio.h>

int HC(int N){
   int g; 
   if (N == 1) return 1;
   else if (N == 2) {
      Guess(1);
      g = Guess(2);
      if(g == 1) return 2;
      else return 1;
   }
   else if (N == 3) {
      Guess(1);
      g = Guess(3);
      if(g == 1) return 3;
      else if(g==-1) return 1;
      else return 2;
   }
   int low = 1;
   int high = N;
   int flag = 1;
   int p; // prev guess Num

   int mid = (low+high) / 2;
   Guess(mid - 1);
   g = Guess(mid +1);

   if(g == 0) return mid;
   else if(g == 1) low = mid+1;
   else high = mid+1;
   p = mid + 1;

   while ( high == N || low == 1 ) {
      // printf("%d %d %d\n", low, high, N);
      if(high == low) return low;
      if( high - low < 3) {
         if(low == 1) {
            g = Guess(1);
            if(g == 1) return 1;
            else if ( g == -1) return high;
            else return 2;
         } else {
            g = Guess(N);
            if(g == 1) return N;
            else if ( g == -1) return low;
            else return N-1;
         }
      }
      if(low == 1) {
         g = Guess(low + (high - low) / 4);
         if(g == 0) {
            return (p + low +(high - low) / 4) >> 1;
         } else if (g < 0 ) {
            int temp = low;
            low = ((p + low + (high - low) / 4) >> 1) + 1;  
            p = temp + (high - temp) / 4;
            break;
         }
         g = Guess(low + (high - low) / 4 + 2);

         if( g == 0 ) return low + (high - low) / 4 + 1;
         else if ( g == -1) {
            high = low + (high - low) / 4 + 2;
            p = high;
            continue;
         } else {
            low = low + (high - low) / 4 + 2;
            p = low;
            break;
         }
      } else {
         g = Guess(high - (high - low) / 4);
         if ( g == 0) {
            return (p + high - (high - low) / 4) >> 1;
         } else if (g < 0) {
            int temp = high;
            high = (p + high - (high - low) / 4 - 1) >> 1;
            p = temp - (temp - low) / 4;            
            break;
         }
         g = Guess(high - (high - low) / 4 - 2);

         if( g == 0 ) return high - (high - low) / 4 - 1;
         else if ( g == -1) {
            low = high - (high - low) / 4 - 2;
            p = low;      
            continue;
         } else {            
            high = high - (high - low) / 4 - 2;
            p = high;
            break;
         }
      }      
   }

   while(high != low) {
      int diff;
      int target;
      if(p <= low) {
         diff = low - p;
         target = high + diff;
      } else if (p >= high) {
         diff = p - high;
         target = low - diff;
      }

      if( target < 1 ) {
         Guess(high);
         p = high;
         continue;
      } 
      if( target > N ) {
         Guess(low);
         p = low;
         continue;
      }

      g = Guess(target);
      if(g == 0) return (high+low) / 2;
      if(g == 1 && target >= high) {
         low = (low + high + 2) / 2;
      } else if ( g == -1 && target >= high) {
         high = (low + high - 1) / 2;
      } else if ( g == 1 && target <= low) {
         high = (low + high - 1) / 2;         
      } else if ( g == -1 && target <= low) {
         low = (low + high + 2) / 2;
      }
      p = target;
   }

   return low;
   // printf("%d %d\n", low, high);
   // return 1;
 
}

Compilation message

hottercolder.c: In function 'HC':
hottercolder.c:22:8: warning: unused variable 'flag' [-Wunused-variable]
   22 |    int flag = 1;
      |        ^~~~
hottercolder.c:119:11: warning: 'target' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |       g = Guess(target);
      |           ^~~~~~~~~~~~~

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	1260 KB	Output is correct

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	1260 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	1260 KB	Output is correct

Subtask #4

5.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	673 ms	9060 KB	Output is partially correct - alpha = 0.200000000000