Submission #592367

# Submission time Handle Problem Language Result Execution time Memory
592367 2022-07-09T05:59:15 Z ogibogi2004 Hotter Colder (IOI10_hottercolder) C++14
81 / 100
2256 ms 8116 KB
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int hist=-1;
int cnt=0;
int hidden,n;
/*int Guess(int g)
{
    if(g<1||g>n)cout<<"err: "<<g<<endl;
    cnt++;
    if(hist==-1)
    {
        hist=g;
        return 0;
    }
    int dist1=abs(hidden-hist),dist2=abs(hidden-g);
    hist=g;
    if(dist1==dist2)return 0;
    if(dist1>dist2)return 1;
    return -1;
}*/
int HC(int N)
{
    srand(69);
    Guess(1);
    int last=1,l=1,r=N;
    while(l<r)
    {
        int mid=r+l-last;
        mid=min(mid,N);
        mid=max(mid,1);
        if(mid==last&&mid+1<=N)mid++;
        if(mid==last&&mid-1>=1)mid--;
        //cout<<l<<" "<<r<<" "<<mid<<endl;
        int t=Guess(mid);
        //cout<<t<<endl;
        int centr=(last+mid)/2;
        if(t==0)
        {
            l=centr;
            r=centr;
        }
        else if(t==1)
        {
            if(last<mid)
            {
                l=max(l,centr+1);
            }
            else
            {
                r=min(r,(last+mid-1)/2);
            }
        }
        else
        {
            if(last<mid)
            {
                r=min(r,(last+mid-1)/2);
            }
            else
            {
                l=max(l,centr+1);
            }
        }
        last=mid;
    }
    return l;
}
# Verdict Execution time Memory Grader output
1 Correct 250 ms 1236 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 236 ms 1276 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 235 ms 1236 KB Output is correct
# Verdict Execution time Memory Grader output
1 Partially correct 2256 ms 8116 KB Output is partially correct - alpha = 0.222222222222