Submission #1248821


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	ll hoge = 1;
	while (hoge * 2 <= n) hoge <<= 1;
	cout << "? " << 0 << " " << hoge << endl;
	ll ans;
	cin >> ans;
	if (n == hoge) {
		cout << "! " << ans << endl;
		return 0;
	}
	int l = hoge, r = n;
	hoge = n - hoge;
	int sign = 1;
	while (true) {
		ll tmp = 1;
		while (tmp * 2 <= hoge) tmp <<= 1;
		if (tmp == hoge) {
			cout << "? " << l << " " << r << endl;
			ll x;
			cin >> x;
			ans += x * sign;
			cout << "! " << ans << endl;
			break;
		}
		bool flag = false;
		if (hoge - tmp >= tmp * 2 - hoge) {
			l = r - tmp * 2;
			flag = true;
		} else {
			r = l + tmp;
		}
		cout << "? " << l << " " << r << endl;
		ll x;
		cin >> x;
		ans += x * sign;
		if (flag) {
			hoge = 2 * tmp - hoge;
			sign *= -1;
			r = l + hoge;
		} else {
			hoge -= tmp;
			l = r;
			r += hoge;			
		}
	}
	return 0;
}

Submission Info

Submission Time
Task A - Array Sum
User fine
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1004 Byte
Status AC
Exec Time 4 ms
Memory 1224 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 24
Set Name Test Cases
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt
Case Name Status Exec Time Memory
01-01.txt AC 3 ms 720 KB
01-02.txt AC 3 ms 716 KB
01-03.txt AC 3 ms 720 KB
01-04.txt AC 3 ms 720 KB
01-05.txt AC 4 ms 1100 KB
01-06.txt AC 4 ms 1096 KB
01-07.txt AC 4 ms 1100 KB
01-08.txt AC 4 ms 972 KB
01-09.txt AC 4 ms 1100 KB
01-10.txt AC 4 ms 1100 KB
01-11.txt AC 4 ms 1096 KB
01-12.txt AC 4 ms 1224 KB
01-13.txt AC 4 ms 1096 KB
01-14.txt AC 4 ms 1224 KB
01-15.txt AC 4 ms 1224 KB
01-16.txt AC 4 ms 1224 KB
01-17.txt AC 4 ms 1220 KB
01-18.txt AC 4 ms 1220 KB
01-19.txt AC 3 ms 848 KB
01-20.txt AC 4 ms 972 KB
01-21.txt AC 4 ms 1224 KB
01-22.txt AC 4 ms 1096 KB
01-23.txt AC 3 ms 972 KB
01-24.txt AC 3 ms 1100 KB