oj.uz

Submission #1038324

# Submission time Handle Problem Language Result Execution time Memory
1038324 2024-07-29T16:37:28 Z huutuan Hotter Colder (IOI10_hottercolder) C++14
87.931 / 100
 461 ms 24552 KB 
#include "grader.h"

#include <bits/stdc++.h>

using namespace std;

int lst;

int guess(int x){
   lst=x;
   return Guess(x);
}

int HC(int N){
   int l=1, r=N;
   while (l<=r){
      int mid=(l+r)>>1;
      if (l==r) return mid;
      int m1=(l+r)>>1, m2=(l+r+1)>>1;
      if (m1==m2) --m1, ++m2;
      // if (lst!=-1 && (m1!=m2 || mid!=lst)){
      //    int t1=0, t2=0, t=0;
      //    if (lst>=m2) t2=lst, t1=m1+m2-lst;
      //    else t1=lst, t2=m1+m2-lst;
      //    if (1<=t1 && 1<=t2 && t1<=N && t2<=N){
      //       if (lst>=m2) t=-guess(t1);
      //       else t=guess(t2);
      //       if (t==0) return mid;
      //       if (t==1) l=mid;
      //       else r=mid;
      //    }
      // }
      guess(m1);
      int t=guess(m2);
      if (!t) return mid;
      if (r-l+1<=3){
         if (t==1) return r;
         return l;
      }
      if (r-l+1==4){
         if (t==1){
            if (guess(r)==1) return r;
            return r-1;
         }else{
            if (guess(l)==1) return l;
            return l+1;
         }
      }
      if (r-l+1==5){
         if (t==1){
            if (guess(r)==1) return r;
            return r-1;
         }else{
            guess(l+1);
            if (guess(l)==1) return l;
            return l+1;
         }
      }
      if (r-l+1==6){
         if (t==1){
            t=guess(r);
            return r-1+t;
         }else{
            t=guess(l+1);
            if (t==0) return l+2;
            if (t==-1) return l+3;
            if (guess(l)==1) return l;
            return l+1;
         }
      }
      if (r-l+1==7){
         if (t==1){
            t=guess(r);
            return r-1+t;
         }else{
            t=guess(l);
            if (t==0) return l+2;
            if (t==-1) return l+3;
            if (guess(l+1)==1) return l+1;
            return l;
         }
      }
      if (t==1){
         l=m2;
         int t=guess(r);
         mid=(l+r)>>1;
         int q1=(l+r)>>1, q2=(l+r+1)>>1;
         if (q1==q2) --q1, ++q2;
         if (!t) return mid;
         if (t==1) l=q2;
         else r=q1;
      }else{
         r=m2;
         int t=-guess(l);
         mid=(l+r)>>1;
         int q1=(l+r)>>1, q2=(l+r+1)>>1;
         if (q1==q2) --q1, ++q2;
         if (!t) return mid;
         if (t==1) l=q2, r=m1;
         else r=q1;
      }
   }
   return -1;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6748 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6748 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6748 KB Output is correct

Subtask #4
12.9310344825 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 461 ms 24552 KB Output is partially correct - alpha = 0.517241379310