AtCoder ABC 299 Find by Query

标签: atinteractivebinary-search

题意

交互题:给定一个 01 序列 ),保证 。你可以询问至多 20 次某个位置的值,求任意一个 使得

解析

考虑二分,如果 ,则说明 中间存在可行的 ,如果 则说明 存在可行

int main()
{
	int n;
	std::cin >> n;
	
	int l = 1, r = n;
	
	std::map<int, int> cache;
	auto ask = [&cache](int pos) mutable -> int
	{
		if (cache.count(pos) != 0) {
			return cache[pos];
		} else {
			std::cout << "? " << pos << std::endl << std::flush;
			int res;
			std::cin >> res;
			cache[pos] = res;
			return res;
		}
	};
	
	while (l < r) {
		int mid = (l + r) / 2;
		int s1 = ask(mid);
		if (s1 == 1) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	std::cout << "! " << r - 1 << std::endl << std::flush;
}