Submission #319694

#	Time	Username	Problem	Language	Result	Execution time	Memory
319694		seedkin	Hotter Colder (IOI10_hottercolder)	C11	75 / 100	718 ms	8804 KiB

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 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;
         }
      } else if ( high - low < 5) {
         if(low == 1) {
            g = Guess(3);            
            if ( g == -1) return high;
            else if (g == 0) return 4;
            g = Guess(1);
            if( g == -1) return 3;
            else if (g == 0) return 2;
            else return 1;
         } else {
            g = Guess(low+2);
            if ( g == -1) return low;
            else if (g == 0) return low + 1;
            g = Guess(high);
            if(g == 1) return high;
            else if ( g == -1) return low+2;
            else return high - 1;
         }
      } else if ( high - low < 7) {
         if(low == 1) {
            g = Guess(5);            
            if ( g == -1) return high;
            else if (g == 0) return 6;
            g = Guess(3);
            if( g == -1) return 5;
            else if (g == 0) return 4;
            g = Guess(1);
            if( g == -1) return 3;
            else if (g == 0) return 2;
            return 1;
         } else {
            g = Guess(low + 2);
            if ( g == -1) return low;
            else if (g == 0) return low + 1;
            g = Guess(low + 4);
            if ( g == -1) return low+2;
            else if (g == 0) return low +3;
            g = Guess(high);
            if ( g == -1) return low+4;
            else if (g == 0) return low +5;
            else return high;
         }
      }
      int size = 1;
      int diff = high - low;
      for(; size < diff; size <<= 1);
      size >>= 1;
      size--;
      if(low == 1) {
         g = Guess(high - size - 2);
         if(g == 0) {
            return (p + high - size - 2) >> 1;
         } else if (g < 0 ) {            
            low = ((p + high - size - 2) >> 1) + 1;  
            p = high - size - 2;
            break;
         }
         g = Guess(high - size);

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

         if( g == 0 ) return low + size + 1;
         else if ( g == -1) {
            low = low + size;
            p = low;      
            continue;
         } else {            
            high = low + size;
            p = high;
            break;
         }
      }      
   }

   while(high != low) {
      // printf("this");
      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; 
}

Compilation message (stderr)

hottercolder.c: In function 'HC':
hottercolder.c:164:11: warning: 'target' may be used uninitialized in this function [-Wmaybe-uninitialized]
  164 |       g = Guess(target);
      |           ^~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 25