oj.uz

답안 #706374

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
706374 2023-03-06T11:38:25 Z SamNguyen Hotter Colder (IOI10_hottercolder) C++14
87 / 100
 502 ms 8112 KB 
#pragma comment(linker, "/STACK:128000000")
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

const int HOTTER = 1, COLDER = -1, SAME = 0;

template <class Func>
int FIND_SMALLEST(int l, int r, Func f) {
	int res = r + 1;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (f(m)) res = m, r = m - 1;
		else l = m + 1;
	}
	return res;
}

template <class Func>
int FIND_LARGEST(int l, int r, Func f) {
	int res = l - 1;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (f(m)) res = m, l = m + 1;
		else r = m - 1;
	}
	return res;
}

template <class T1, class T2>
inline int minimise(T1 &x, T2 y) {
	if (x > y) { x = y; return true; }
	return false;
}

template <class T1, class T2>
inline int maximise(T1 &x, T2 y) {
	if (x < y) { x = y; return true; }
	return false;
}

const int INF = 0x2f2f2f2f;
int N;
mt19937 rnd(time(NULL));

int solve(int l, int r, int x) {
	//cout << "solve " << l << " " << r << ", x = " << x << endl;

	if (l > r)
		return -1;

	if (l == r)
		return r;

	int y = l + r - x;
	if (y < 1 or y > N)
		y = (l + r) >> 1;
	
	if (y == x) {
		if (y == 1)
			y++;
		else
			y--;
	}

	int m1 = (x + y) >> 1;
	int m2 = (x + y + 1) >> 1;

	int id = Guess(y);
	if (id == SAME)
		return m1;

	if (id == HOTTER)
		return x < y ? solve(m1 + 1, r, y) : solve(l, m2 - 1, y);

	if (id == COLDER)
		return x < y ? solve(l, m2 - 1, y) : solve(m1 + 1, r, y);

	return -1;
}

int HC(int _N) {
	N = _N;
	if (N == 1)
		return 1;
	
	if (N == 2) {
		Guess(1);
		if (Guess(2) == HOTTER)
			return 2;
		return 1;
	}

	int x = max(1, 2 * N / 5);
	Guess(x);
	return solve(1, N, x);
}

Compilation message

hottercolder.cpp:1: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    1 | #pragma comment(linker, "/STACK:128000000")
      |

Subtask #1
25.0 / 25.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
12.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 502 ms 8112 KB Output is partially correct - alpha = 0.500000000000