oj.uz

Submission #205059

# Submission time Handle Problem Language Result Execution time Memory
205059 2020-02-27T20:13:34 Z mode149256 Hotter Colder (IOI10_hottercolder) C++14
78 / 100
 943 ms 8188 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1272 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1272 KB Output is correct

Subtask #4
3.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 943 ms 8188 KB Output is partially correct - alpha = 0.120000000000