oj.uz

Submission #1012695

# Submission time Handle Problem Language Result Execution time Memory
1012695 2024-07-02T13:52:42 Z bachhoangxuan Hotter Colder (IOI10_hottercolder) C++17
100 / 100
 520 ms 24544 KB 
#include "grader.h"
#include<bits/stdc++.h>

int HC(int N){
    std::function<int(int)> f = [&](int n){
        return (n<5?1:(n+1>>1)-f(n>>1));
    };
    int l=1,r=N,w=log(3*N)/log(2);
    while(l<r){
        if(r==2){
            Guess(1);
            return (Guess(2)<0?1:2);
        }
        int s=(2<<(w-2))/3+2-(w&1);
        int y=(r==N)?s+f(r-s):2*s-1,x=2*s-y;
        Guess(x);
        int k=Guess(y);
        if(k==-1) r=x+y-1>>1;
        else if(k==0) return x+y>>1;
        else{
            l=x+y+2>>1;x=y;
            while(l<r){
                y=((l+r)>>1<<1)-x;
                if(x==y) y++;
                y=std::min(N,std::max(y,1));
                k=Guess(y);
                if(k==0) return x+y>>1;
                else if((k==1)^(x>y)) l=x+y+2>>1;
                else r=x+y-1>>1;
                x=y;
            }
        }
        w-=2;
    }
    return l;
}

Compilation message

hottercolder.cpp: In lambda function:
hottercolder.cpp:6:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 |         return (n<5?1:(n+1>>1)-f(n>>1));
      |                        ~^~
hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:18:24: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   18 |         if(k==-1) r=x+y-1>>1;
      |                     ~~~^~
hottercolder.cpp:19:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         else if(k==0) return x+y>>1;
      |                              ~^~
hottercolder.cpp:21:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |             l=x+y+2>>1;x=y;
      |               ~~~^~
hottercolder.cpp:27:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |                 if(k==0) return x+y>>1;
      |                                 ~^~
hottercolder.cpp:28:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |                 else if((k==1)^(x>y)) l=x+y+2>>1;
      |                                         ~~~^~
hottercolder.cpp:29:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   29 |                 else r=x+y-1>>1;
      |                        ~~~^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1372 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1368 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1372 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 24544 KB Output is partially correct - alpha = 1.000000000000