Submission #1038277

---

Source Code Expand

#include <cstdlib>
#include <iostream>
#include <vector>

int findMinNum(int a) {
	while (a&(a - 1)) a = a&(a - 1);
	return a;
}

int N;

int question_start = 0;
int question_end = 0;
int range = 0;
int answer = 0;
int temp = 0;

int question(int l, int r){
	question_start = l; question_end = r;
	std::cout << "? " << question_start << " " << question_end << std::endl;
	std::cin >> temp;
	return temp;
}

bool dfs(int l, int r, int nokori, int flag){
	std::cerr << l << " " << r << " " << nokori << " " << flag << std::endl;
	int nr, nl;
	if (r == l) return true;
	if (nokori == 0) return false;

	//small side
	int dist = findMinNum(r - l);
	nl = l + dist;
	nr = r;
	if(dfs(nl, nr, nokori-1, flag)){
		answer += question(l, l + dist) * flag;
		return true;
	}

	dist *= 2;

	nl = r - dist;
	nr = l;
	if (dfs(nl, nr, nokori - 1, -flag)) {
		answer += question(r - dist, r) * flag;
		return true;
	}

	return false;
}

int main() {
	//まず，数列の長さを表す整数 N が標準入力に与えられる．
	std::cin >> N;

	//最初に最大の2の冪の質問をする
	for (int i = 1; i <= N; i *= 2) {
		question_end = i;
	}
	range = question_end - question_start;
	std::cout << "? 0 " << question_end << std::endl;
	std::cin >> temp;
	answer += temp;

	//最初で全ての答えを求められた場合、終了する
	if (question_end == N) {
		std::cout << "! " << answer << std::endl;
		return EXIT_SUCCESS;
	}

	int start = question_end;
	int end = N;
	int flag = 1;
	dfs(start, end, 8, flag);

	//次に最大の2の冪まで計算する
	std::cout << "! " << answer << std::endl;
	return EXIT_SUCCESS;
}

Submission Info

Judge Result