Submission #1260488

---

Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;
int n, b[100009], dp[100009];
int solve(int l, int r) {
	if (l == r) return 0;
	int x = r - l, v1, v2;
	cout << "? " << l << ' ' << l + (1 << b[x]) << endl;
	cin >> v1;
	if (dp[x - (1 << b[x])] + 1 == dp[x]) return v1 + solve(l + (1 << b[x]), r);
	cout << "? " << r - (1 << b[x]) << ' ' << r << endl;
	cin >> v2;
	return v1 + v2 - solve(r - (1 << b[x]), l + (1 << b[x]));
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		while (1 << b[i] <= i) b[i]++; b[i]--;
		dp[i] = min(dp[i - (1 << b[i])] + 1, dp[(2 << b[i]) - i] + 2);
	}
	int ret = solve(0, n);
	cout << "! " << ret << endl;
	return 0;
}

Submission Info

Judge Result