oj.uz

Submission #706370

# Submission time Handle Problem Language Result Execution time Memory
706370 2023-03-06T11:23:52 Z SamNguyen Hotter Colder (IOI10_hottercolder) C++14
75 / 100
 10000 ms 9400 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 opt_y = -1, diff = INF;

	for (int y = 1; y <= N; y++) if (y != x) {
		int m1 = (x + y) >> 1;
		int m2 = (x + y + 1) >> 1;

		int len_1 = m2 - l;
		int len_2 = r - m1;

		if (minimise(diff, abs(len_1 - len_2)))
			opt_y = y;
	}

	if (opt_y == -1) {
		cout << "No opt_y found." << endl;
		return -1;
	}

	return [&](int 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;
	}(opt_y);
}

int HC(int _N) {
	N = _N;
	if (N == 1)
		return 1;

	Guess(N / 2);
	return solve(1, N, N / 2);
}

Compilation message

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 1288 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 1288 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 1288 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10045 ms 9400 KB Time limit exceeded