oj.uz

Submission #748829

# Submission time Handle Problem Language Result Execution time Memory
748829 2023-05-27T04:24:53 Z wenqi Hotter Colder (IOI10_hottercolder) C++17
52 / 100
 556 ms 24388 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)
{
	int m = (l + r) / 2;
	int w = 2 * m - 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 (q < m)
	{
		if (g == 0)
			return m;
		if (g == 1)
			return search(m + 1, r, w);
		return search(l, m - 1, w);
	}
	if (g == 0)
		return m;
	if (g == -1)
		return search(m + 1, r, w);
	return search(l, m - 1, 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 20 ms 1364 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
0 / 25.0

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

Subtask #4
2.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 556 ms 24388 KB Output is partially correct - alpha = 0.080000000000