Submission #903826

#	Time	Username	Problem	Language	Result	Execution time	Memory
903826		abcvuitunggio	Hotter Colder (IOI10_hottercolder)	C++17	91 / 100	762 ms	8328 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 sz=1;
    while (sz<r-l+1)
        sz=sz*2+1;
    sz/=2;
    int mid=0;
    if (last<=l)
        mid=r-sz+1;
    else if (last>=r)
        mid=l+sz-1;
    else
        mid=(l+r)/2;
    if (mid==last)
        mid++;
    int nxt=mid*2-last;
    nxt=max(nxt,1);
    nxt=min(nxt,n);
    if (nxt%2!=last%2)
        nxt+=(nxt==1)*2-1;
    int x=Guess(nxt);
    mid=(nxt+last)/2;
    if (!x)
        return mid;
    if ((x>0&&nxt>last)||(x<0&&nxt<last))
        return g(min(mid+1,r),r,nxt);
    return g(l,max(mid-1,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<8){
        int x=Guess(calc(1,e));
        if (!x)
            return calc(4,e);
        if (x>0)
            return calc(Guess(calc(3,e))+2,e);
        return calc(Guess(calc(n*2-3,e))+n-1,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]=7;
    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: 16 / 25