oj.uz

답안 #836411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836411 2023-08-24T10:57:49 Z finn__ Hotter Colder (IOI10_hottercolder) C++17
82 / 100
 491 ms 8108 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 ((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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 1236 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 1304 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1300 KB Output is correct

Subtask #4
7.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 491 ms 8108 KB Output is partially correct - alpha = 0.285714285714