Submission #903727

#	Time	Username	Problem	Language	Result	Execution time	Memory
903727		abcvuitunggio	Hotter Colder (IOI10_hottercolder)	C++17	0 / 100	532 ms	24612 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),mid=(last+x)/2;
    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);
    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,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(0);
        return (Guess(1)+1)/2;
    }
    dp[0]=1;
    dp[1]=3;
    for (int i=2;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);
}

Compilation message (stderr)

hottercolder.cpp: In function 'int g(int, int, int)':
hottercolder.cpp:20:12: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |     if (x>0&&nxt>last||x<0&&nxt<last)
      |         ~~~^~~~~~~~~~
hottercolder.cpp:17:22: warning: unused variable 'mid' [-Wunused-variable]
   17 |     int x=Guess(nxt),mid=(last+x)/2;
      |                      ^~~

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