Submission #941791

#	Time	Username	Problem	Language	Result	Execution time	Memory
941791		benjaminkleyn	Hotter Colder (IOI10_hottercolder)	C++17	0 / 100	493 ms	74068 KiB

hottercolder

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;

int n;
int search(int lo, int hi, int prev_guess)
{
    if (lo == hi)
        return lo;
    if (lo + 1 == hi)
    {
        Guess(lo);
        if (Guess(hi) > 1)
            return hi;
        return lo;
    }
    if (lo + 2 == hi)
    {
        Guess((lo + hi) / 2);
        if (Guess(lo) > 1)
            return lo;
        if (Guess(hi) > 1)
            return hi;
        return (lo + hi) / 2;
    }
    // we know that the previous guess was 'prev_guess',
    // so our next guess can maybe always cut the search space in two?
    int next_guess = lo + hi - prev_guess;
    if (next_guess < 1 || n < next_guess)
    {
        Guess(lo);
        prev_guess = lo;
        next_guess = hi;
    }
    int result = Guess(next_guess);
    int m1 = (prev_guess + next_guess) / 2;
    int m2 = (prev_guess + next_guess + 1) / 2;
    if (result == 0)
        return m1;
    if ((next_guess < prev_guess && result < 0) || (prev_guess < next_guess && result > 0))
        return search(max(lo, m2), hi, next_guess);
    return search(lo, min(hi, m1), next_guess);
}

int HC(int N)
{
    n = N;
    Guess((2 + N) / 3);
    return search(1, N, 1);
}

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