oj.uz

Submission #1018486

# Submission time Handle Problem Language Result Execution time Memory
1018486 2024-07-10T06:15:54 Z socpite Hotter Colder (IOI10_hottercolder) C++14
91.6667 / 100
 437 ms 8048 KB 
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(69420);

int n;

int solve(int l, int r, int prv){
   // cout << l << " " << r << " " << prv << endl;
   if(l == r)return l;
   if(l == 1){
      if(r <= 3){
         int tmp = Guess(1);
         if(tmp == 1)return 1;
         if(tmp == 0)return 2;
         return r;
      }
      int dist = (r - l + 1)/4, g = max(1, dist - 2);
      int tmp = Guess(g);
      if(tmp == -1)return solve((g+r)/2 + 1, r, g);
      if(tmp == 0)return (g+r)/2;
      tmp = Guess(g+2);
      if(tmp == 0)return g+1;
      if(tmp == -1)return solve(1, g+2, g+2);
      return solve(g+2, (g+r-1)/2, g+2);
   }
   else if(r == n){
      if(r - l + 1 <= 3){
         int tmp = Guess(n);
         if(tmp == 1)return n;
         if(tmp == 0)return n-1;
         return l;
      }
      int dist = (r - l + 1)/4, g = min(n, r - dist + 3);
      int tmp = Guess(g);
      if(tmp == -1)return solve(l, (l+g-1)/2, g);
      if(tmp == 0)return (l+g)/2;
      tmp = Guess(g-2);
      if(tmp == 0)return g-1;
      if(tmp == -1)return solve(g-2, r, g-2);
      return solve((g+l)/2 + 1, g-2, g-2);
   }
   else {
      int mid = (l+r)>>1;
      if(prv == mid){
         int tmp = Guess(prv + 2);
         if(tmp == -1)return solve(l, prv, prv+2);
         if(tmp == 0)return prv+1;
         if(tmp == 1)return solve(prv+2, r, prv+2);
      }
      int qq = max(1, 2*mid - prv);
      qq = min(qq, n);
      int tmp = Guess(qq);
      if(prv < mid)tmp*=-1;
      if(tmp == -1)return solve((qq + prv)/2 + 1, r, qq);
      if(tmp == 0)return (qq+prv)/2;
      return solve(l, (qq+prv-1)/2, qq);
   }
}

int HC(int N){
   n = N;
   if(n <= 3){
      Guess(n);
      return solve(1, n, 1);
   }
   else {
      int mid = n/2;
      Guess(mid-1);
      int tmp = Guess(mid+1);
      if(tmp == 0)return mid;
      if(tmp == 1)return solve(mid+1, n, mid+1);
      return solve(1, mid+1, mid+1);
   }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 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 16 ms 6748 KB Output is correct

Subtask #4
16.6666666675 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 437 ms 8048 KB Output is partially correct - alpha = 0.666666666667