oj.uz

Submission #1074604

# Submission time Handle Problem Language Result Execution time Memory
1074604 2024-08-25T11:23:13 Z beaconmc Hotter Colder (IOI10_hottercolder) C++14
77.8846 / 100
 2521 ms 8240 KB 
#include "grader.h"
    #include <bits/stdc++.h>
     
    typedef long long ll;
     
    #define FOR(i,x,y) for(ll i=x; i<y; i++)
    #define FORNEG(i,x,y) for(lli = x; i>y; i--)
    using namespace std;
     
     
    ll n;
    map<ll,ll> sus;
    ll cnt = 0;
    ll idkman = -1;
    int guess(ll a){
     
       if (a==0) return -1;
       if (a==n+1) return -1;
       cnt++;
       idkman = a;
       return Guess(a);
     
    }
    int solve(int a, int b){
       if (a==b) return a;
       
       ll lmao = rand()%2;
       // cout << lmao << endl;
       // cout << a << " " << b << endl;
     
       
       if (idkman == (a+b)/2  && n>500){
          // cout << "LMAO" << endl;
          ll mid = idkman;
          ll right = guess(idkman+1);
          if (right == -1){
             return solve(a, mid);
          }else{
             return solve(mid+1, b);
          }
       }
       else if (idkman == (a+b)/2-1  && n>500){
          // cout << "LMAO" << endl;
          ll mid = idkman;
          ll right = guess(idkman+1);
          if (right == -1){
             return solve(a, mid);
          }else{
             return solve(mid+1, b);
          }
       }
       else{
     
          if (lmao == 0){
             ll mid = (a+b)/2;
             ll midleft = (a+mid)/2;
             ll midright = (b+mid+1)/2;
     
             ll left, right;
             left = guess(midleft);
             right = guess(midright);
             if (right == 0 ){
                return (midleft+midright)/2;
             }
             else if (right == -1){
                if ((midleft+midright)%2==0) return solve(a, mid-1);
                return solve(a,mid);
             }else{
                return solve(mid+1, b);
             }
          } else{
             ll mid = (a+b)/2;
             ll midleft = (a+mid)/2;
             ll midright = (b+mid+1)/2;
     
             ll left, right;
             right = guess(midright);
             left = guess(midleft);
             
             if (left == 0 ){
                return (midleft+midright)/2;
             }
             else if (left == -1){
                return solve(mid+1, b);
             }else{
                if ((midleft+midright)%2==0 && n<=500) return solve(a, mid-1);
                return solve(a,mid);
             }
          }
     
     
       }
    }
     
     
    int HC(int N){
       idkman = -1;
       srand(N+12363);
       sus.clear();
       n = N;
       cnt = 0;
       ll ans = solve(1,N);
 
       return ans;
    }

Compilation message

hottercolder.cpp: In function 'int solve(int, int)':
hottercolder.cpp:59:17: warning: variable 'left' set but not used [-Wunused-but-set-variable]
   59 |              ll left, right;
      |                 ^~~~
hottercolder.cpp:76:23: warning: variable 'right' set but not used [-Wunused-but-set-variable]
   76 |              ll left, right;
      |                       ^~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
2.884615385 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 2521 ms 8240 KB Output is partially correct - alpha = 0.115384615385