Submission #706374

#	Time	Username	Problem	Language	Result	Execution time	Memory
706374		SamNguyen	Hotter Colder (IOI10_hottercolder)	C++14	87 / 100	502 ms	8112 KiB

hottercolder

#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 (stderr)

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

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 12 / 25