oj.uz

Submission #941789

# Submission time Handle Problem Language Result Execution time Memory
941789 2024-03-09T12:11:49 Z benjaminkleyn Hotter Colder (IOI10_hottercolder) C++17
0 / 100
 10000 ms 22624 KB 
#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 = max(1, min(n, lo + hi - prev_guess));
    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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10001 ms 6904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10027 ms 6744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10047 ms 6744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10013 ms 22624 KB Time limit exceeded
2 Halted 0 ms 0 KB -