oj.uz

답안 #903742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
903742 2024-01-11T11:00:53 Z abcvuitunggio Hotter Colder (IOI10_hottercolder) C++17
0 / 100
 543 ms 8236 KB 
#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==4||n==5){
        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);
    }
    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(1);
        return (Guess(2)+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);
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 6768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 6760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 6760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 543 ms 8236 KB Output isn't correct - alpha = 0.000000000000