Submission #116143

#	Time	Username	Problem	Language	Result	Execution time	Memory
116143		eriksuenderhauf	Hotter Colder (IOI10_hottercolder)	C++11	94 / 100	814 ms	8296 KiB

hottercolder

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int n = 0;

int solve(int lo, int hi, int pre) {
	if (lo == hi) return lo;
	//cout << lo << " " << hi << " " << pre << "\n";
	if (lo == 1) {
		if (hi == 1) return 1;
		Guess(1);
		if (hi == 2) {
			int g = Guess(2);
			if (g == -1)
				return 1;
			return 2;
		}
		if (hi == 3) {
			int g = Guess(3);
			if (g == 0) return 2;
			else if (g == 1) return 3;
			return 1;
		}
		if (hi == 4) {
			int g = Guess(3);
			if (g == 0) return 2;
			else if (g == -1) return 1;
			g = Guess(4);
			if (g == 1) return 4;
			return 3;
		}
		if (hi == 5) {
			int g = Guess(3);
			if (g == 0) return 2;
			else if (g == -1) return 1;
			g = Guess(5);
			if (g == 1) return 5;
			else if (g == 0) return 4;
			return 3;
		}
		if (hi == 6) {
			int g = Guess(3);
			if (g == 0) return 2;
			else if (g == -1) return 1;
			g = Guess(5);
			if (g == 0) return 4;
			else if (g == -1) return 3;
			g = Guess(6);
			if (g == 1) return 6;
			return 5;
		}
		if (hi == 7) {
			int g = Guess(3);
			if (g == 0) return 2;
			else if (g == -1) return 1;
			g = Guess(5);
			if (g == 0) return 4;
			else if (g == -1) return 3;
			g = Guess(7);
			if (g == 1) return 7;
			else if (g == 0) return 6;
			return 5;
		}
		if (hi == 8) {
			int g = Guess(6);
			if (g == -1) return solve(1, 3, 6);
			g = Guess(8);
			if (g == 0) return 7;
			else if (g == 1) return 8;
			g = Guess(2);
			if (g == 1) return 4;
			else if (g == 0) return 5;
			return 6;
		}
		int idx = (lo+hi+1) / 2;
		int g = Guess(idx);
		if (g == 0) return (idx+lo)/2;
		else if (g == -1) return solve(lo, (idx+lo-1)/2, idx);
		return solve((idx+lo)/2+1,hi, idx);
	}
	if (pre == lo) {
		int g = Guess(hi);
		if (g == 0)
			return (lo + hi) / 2;
		if (g < 0)
			return solve(lo, (lo + hi - 1) / 2, hi);
		return solve((lo + hi) / 2 + 1, hi, hi);
	} else if (pre == hi) {
		int g = Guess(lo);
		if (g == 0)
			return (lo + hi) / 2;
		if (g > 0)
			return solve(lo, (lo + hi - 1) / 2, lo);
		return solve((lo + hi) / 2 + 1, hi, lo);
	}
	//cout << "next query: " << 2 * mi - pre << " " << mi << "\n";
	int idx = (lo + hi - pre);
	if (idx == pre)
		idx++;
	idx = max(1, min(n, idx));
	int g = Guess(idx);
	if (g == 0)
		return (idx + pre) / 2;
	if (g > 0 && idx > pre)
		return solve((idx + pre) / 2 + 1, hi, idx);
	if (g > 0 && idx < pre)
		return solve(lo, (idx + pre - 1) / 2, idx);
	if (g < 0 && idx > pre)
		return solve(lo, (idx + pre - 1) / 2, idx);
	if (g < 0 && idx < pre)
		return solve((idx + pre) / 2 + 1, hi, idx);
}

int HC(int N) {
	n = N;
	int ans = solve(1, n, 0);
	//cout << "answer: " << ans << "\n";
	return ans;
}

Compilation message (stderr)

hottercolder.cpp: In function 'int solve(int, int, int)':
hottercolder.cpp:112:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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