oj.uz

답안 #1074552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074552 2024-08-25T11:06:38 Z beaconmc Hotter Colder (IOI10_hottercolder) C++14
77.5862 / 100
 2493 ms 22388 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 && (b-a+1)>10){
          // 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(time(0));
       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:49:17: warning: variable 'left' set but not used [-Wunused-but-set-variable]
   49 |              ll left, right;
      |                 ^~~~
hottercolder.cpp:66:23: warning: variable 'right' set but not used [-Wunused-but-set-variable]
   66 |              ll left, right;
      |                       ^~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 1368 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 1416 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 250 ms 1372 KB Output is correct

Subtask #4
2.5862068975 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2493 ms 22388 KB Output is partially correct - alpha = 0.103448275862