Submission #836411

#	Time	Username	Problem	Language	Result	Execution time	Memory
836411		finn__	Hotter Colder (IOI10_hottercolder)	C++17	82 / 100	491 ms	8108 KiB

hottercolder

#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 ((j - i) * 4 < N)
        {
            if ((i - 1) * 20 < N)
                mid = (6 * i + 4 * j) / 10;
            else if ((N - j) * 20 < N)
                mid = (4 * i + 6 * j) / 10;
        }
        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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 7 / 25