oj.uz

Submission #748834

# Submission time Handle Problem Language Result Execution time Memory
748834 2023-05-27T04:33:53 Z wenqi Hotter Colder (IOI10_hottercolder) C++17
50 / 100
 546 ms 8188 KB 
#include "grader.h"
#include <algorithm>
#include <iostream>
using namespace std;

int R(int, int);

int L(int l, int r)
{
	if (l == r)
		return l;
	int g = Guess(r);
	if (g == 0)
	{
		return (l + r) / 2;
	}
	if (g == 1)
	{
		return R((l + r) / 2 + 1, r);
	}
	Guess(l);
	return L(l, (l + r - 1) / 2);
}

int R(int l, int r)
{
	if (l == r)
		return l;
	int g = Guess(l);
	if (g == 0)
	{
		return (l + r) / 2;
	}
	if (g == 1)
	{
		return L(l, (l + r - 1) / 2);
	}
	Guess(r);
	return R((l + r) / 2 + 1, r);
}

int N;

int search(int l, int r, int q)
{
	if (l == r)
		return l;
	int m = (l + r) / 2;
	int w = l + r - q;
	w = clamp(w, 1, N);
	// printf("%d %d %d %d\n", l, r, q, w);
	m = (w + q) / 2;
	int g = Guess(w);
	if (2 * q < l + r)
	{
		if (g == 0)
			return m;
		if (g == 1)
			return search(m + 1, r, w);
		return search(l, m, w);
	}
	if (g == 0)
		return m;
	if (g == -1)
		return search(m + 1, r, w);
	return search(l, m, w);
}

int HC(int N_)
{
	N = N_;
	Guess(1);
	// int guess = L(1, N);
	int guess = search(1, N, 1);
	return guess;
}

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 22 ms 1300 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 1300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 546 ms 8188 KB Output isn't correct - alpha = 0.000000000000