oj.uz

Submission #903839

# Submission time Handle Problem Language Result Execution time Memory
903839 2024-01-11T12:03:36 Z abcvuitunggio Hotter Colder (IOI10_hottercolder) C++17
100 / 100
 629 ms 8232 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 sz=1;
    while (sz<r-l+1)
        sz=sz*2+1;
    int mid=0;
    if (last<=r-sz)
        mid=r-sz/2;
    else if (last>=l+sz)
        mid=l+sz/2;
    else if (last<=l)
        mid=last+sz/2;
    else
        mid=last-sz/2;
    int nxt=mid*2-last;
    int x=Guess(nxt);
    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;
    }
    if (N<6){
        Guess(N);
        return f(N,1);
    }
    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=(N+2)/2;
    Guess(mid-2);
    int x=Guess(mid);
    if (!x)
        return mid-1;
    if (x<0)
        return f(mid,1);
    return f(N-mid+1,N);
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6900 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6744 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6768 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 629 ms 8232 KB Output is partially correct - alpha = 1.000000000000