oj.uz

Submission #836390

# Submission time Handle Problem Language Result Execution time Memory
836390 2023-08-24T10:49:34 Z finn__ Hotter Colder (IOI10_hottercolder) C++17
82 / 100
 479 ms 24416 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

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

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

        int 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 17 ms 1304 KB Output is correct

Subtask #2
25.0 / 25.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
7.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 479 ms 24416 KB Output is partially correct - alpha = 0.296296296296