Submission #1074229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074229		Hugo1729	Hotter Colder (IOI10_hottercolder)	C++11	25 / 100	600 ms	24356 KiB

hottercolder

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

int p;

int make_guess(int x){
   int sus = Guess(x);
   //cout << x << ' ' << sus << '\n';
   return sus;
}

int HC(int N){
   // int g = make_guess(1);
   // int h = make_guess(N);
   // if (g == 0) return N/2;
   // if (g < 0) return N/4;
   // if (g > 0) return 3*N/4;

   //cout << N << '\n';

   p=-1;

   int lo=1,hi=N;

   while(lo<hi){
      int mid=(hi+lo)/2;

      if(p==-1){
         int g1 = make_guess(mid),g2=make_guess(mid+1);
         p=mid+1;

         if(g2==1){
            lo=mid+1;
         }else{
            hi=mid;
         }
      }else{
         int query=min(N,max(1,(lo+hi-p)));
         if(hi-lo>3){
            int next_query2=((p+query+1)/2+hi-query),next_query1=((p+query)/2+lo-query);
            //cout << "b: " << next_query1 << ' ' << next_query2 << '\n';
            if(next_query1<1){
               query+=next_query1-1;
            }
            else if(next_query2>N){
               query+=(N-next_query2);
            }
         }
         if(query<1||query>N||query==p){
               if(p<=(lo+hi)/2){
                  query=p+1;
               }else{
                  query=p-1;
               }
            }

         //cout << query << '\n';
         int g=make_guess(query);

         if(g==0){
            //cout << (query+p)/2 << "\n\n";
            return (query+p)/2;
         }
         else if(query<p){
            if(g==1)hi=min(hi,(p+query)/2);
            else lo=max(lo,(p+query+1)/2);
         }else{
            if(g==-1)hi=min(hi,(p+query)/2);
            else lo=max(lo,(p+query+1)/2);
         }

         p=query;
      }
      //cout << "a: " << lo << ' ' << hi << '\n';
   }

   //cout << lo << "\n\n";

   return lo;
}

Compilation message (stderr)

hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:30:14: warning: unused variable 'g1' [-Wunused-variable]
   30 |          int g1 = make_guess(mid),g2=make_guess(mid+1);
      |              ^~

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