Submission

(PPPPP)

Score: 100

User: njoop

Problemset: Ice cream

Language: cpp

Time: 0.001 second

Submitted On: 2025-04-21 02:16:47

#include "ice_cream.h"

using namespace std;

int fib[20];

int find_min_fib(int x) {
    int t=2;
    while(x > fib[t]) {
        t++;
    }
    t -= 2;
    return fib[t];
}

int guess(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for(int i=2; i<=19; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    int l=1, r=n;
    while(l < r-1) {
        int mid = l + find_min_fib(r-l) - 1;
        if(ask(1, mid)) {
            r = mid;
        } else {
            l = mid+1;
        }
    }
    if(l == r) return l;
    else if(ask(l, l)) return l;
    else return r;
}