Submission #205059

#	Time	Username	Problem	Language	Result	Execution time	Memory
205059		mode149256	Hotter Colder (IOI10_hottercolder)	C++14	78 / 100	943 ms	8188 KiB

hottercolder

#include <algorithm>
#include "grader.h"
#include <cassert>
#include <iostream>
#include <cmath>

using namespace std;


int ct;

int HC(int n){
	int low,high,mid,g,prev,use;

	ct = 0;
	low = 1;
	high = n;
	use = 0;
	prev = -1;

	while(low < high){
		mid = low + (high-low)/2;

		if(!use){
			prev = rand()%2 ? low : high;
			use = 1;
			Guess(prev);
		}

		g = Guess(prev^low^high);
		g *= (prev == low ? 1 : -1);
		prev = prev^low^high;
		++ct;

		if(!g){
			assert(mid-low == high-mid);
			return mid;
		}

		if(g > 0){
			low = mid+1;
			use = prev == high;
		}else{
			high = (low+high+1)/2-1;
			use = prev == low;
		}
	}

	return low;
}

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