Submission #903778

#	Time	Username	Problem	Language	Result	Execution time	Memory
903778		abcvuitunggio	Hotter Colder (IOI10_hottercolder)	C++17	92 / 100	602 ms	16684 KiB

hottercolder

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int n;
long long dp[40];
int calc(int n, int e){
    return (e==1?n:e-n+1);
}
int g(int l, int r, int last){
    if (l==r)
        return l;
    if (l>r)
        swap(l,r);
    int nxt=l+r-last;
    nxt=max(nxt,1);
    nxt=min(nxt,n);
    int x=Guess(nxt);
    if (!x)
        return (last+nxt)/2;
    if ((x>0&&nxt>last)||(x<0&&nxt<last))
        return g(min((last+nxt)/2+1,r),r,nxt);
    return g(l,max((last+nxt-1)/2,l),nxt);
}
int f(int n, int e){
    if (n==1)
        return e;
    if (n==2)
        return calc((3-Guess(e))/2,e);
    if (n==3)
        return calc(2-Guess(e),e);
    if (n<6){
        int x=Guess(calc(n-2,e));
        if (!x)
            return calc(n-1,e);
        if (x<0)
            return calc(n,e);
        return f(n-2,e);
    }
    if (n==6){
        int x=Guess(calc(1,e));
        if (x>0)
            return calc(Guess(calc(3,e))+2,e);
        return calc(Guess(calc(9,e))+5,e);
    }
    int i=lower_bound(dp,dp+40,n)-dp-2;
    int x=Guess(calc(dp[i]-2,e));
    if (!x)
        return calc((dp[i]+n-2)/2,e);
    if (x<0)
        return g(calc((dp[i]+n-2)/2+1,e),calc(n,e),calc(dp[i]-2,e));
    x=Guess(calc(dp[i],e));
    if (!x)
        return calc(dp[i]-1,e);
    if (x<0)
        return f(dp[i],e);
    return g(calc(dp[i],e),calc((dp[i]+n-3)/2,e),calc(dp[i],e));
}
int32_t HC(int32_t N){
    n=N;
    if (N==1)
        return 1;
    if (N==2){
        Guess(1);
        return (Guess(2)+3)/2;
    }
    dp[0]=1;
    dp[1]=3;
    dp[2]=6;
    for (int i=3;i<40;i++)
        dp[i]=dp[i-2]+(1LL<<i);
    int mid=(1+N)>>1;
    Guess(mid-1);
    int x=Guess(mid+1);
    if (!x)
        return mid;
    if (x<0)
        return f(mid+1,1);
    return f(N-mid,N);
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 17 / 25