oj.uz

Submission #836403

# Submission time Handle Problem Language Result Execution time Memory
836403 2023-08-24T10:53:54 Z finn__ Hotter Colder (IOI10_hottercolder) C++17
80 / 100
 483 ms 8100 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

int HC(int N_)
{
    int64_t N = N_, i = 1, j = N, k = 1 + (N * 95) / 100;
    Guess(k);

    while (i < j)
    {
        int64_t mid = (i + j) / 2;
        if ((i - 1) * 20 < N)
            mid = (75 * i + 25 * j) / 100;
        else if ((N - j) * 20 < N)
            mid = (25 * i + 75 * j) / 100;
        int64_t q;
        if (i == 1 && j == N)
            q = min(1 + (N * 55) / 100, k - 1);
        else
        {
            if (k < mid)
                q = min(N, mid + (mid - k));
            else if (k > mid)
                q = max((int64_t)1, mid - (k - mid));
            else
                q = mid + 1 <= N ? mid + 1 : mid - 1;
        }

        int64_t x = Guess(q);

        if (!x)
        {
            return min(k, q) + abs(k - q) / 2;
            return 0;
        }
        if (x == 1)
        {
            if (q < k)
                j = k - (k - q) / 2 - 1;
            else
                i = k + (q - k) / 2 + 1;
        }
        else
        {
            if (q < k)
                i = q + (k - q) / 2 + 1;
            else
                j = q - (q - k) / 2 - 1;
        }

        k = q;
    }

    return i;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1236 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1236 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1236 KB Output is correct

Subtask #4
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 483 ms 8100 KB Output is partially correct - alpha = 0.185185185185