Submission #1260516


Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
pair<vector<pair<int, int>>, int>dp[100005]; int n;
int solve(int pos) {
	if (pos == 0)return 0;
	if (dp[pos].second >= 1)return dp[pos].second;
	int minx = 100000; vector<pair<int, int>>minid;
	for (int i = 0; i < 20; i++) {
		if ((1 << i) > pos)continue;
		int G = solve(pos - (1 << i));
		if (G + 1 < minx) { minx = G + 1; minid = dp[pos - (1 << i)].first; minid.push_back(make_pair(i, -1)); }
	}
	for (int i = 0; i < 20; i++) {
		for (int j = 0; j < 20; j++) {
			if ((1 << i) >= pos || (1 << j) >= pos || (1 << i) + (1 << j) <= pos)continue;
			int G = solve((1 << i) + (1 << j) - pos);
			if (G + 2 < minx) { minx = G + 2; minid = dp[(1 << i) + (1 << j) - pos].first; minid.push_back(make_pair(i, j)); }
		}
	}
	dp[pos] = make_pair(minid, minx);
	return minx;
}
int sum(int pos, int L, int R) {
	if (pos == dp[n].first.size())return 0;
	int B1 = dp[n].first[pos].first, B2 = dp[n].first[pos].second;
	if (B2 == -1) {
		cout << "? " << L << ' ' << L + (1 << B1) << endl;
		int s; cin >> s;
		return s + sum(pos + 1, L + (1 << B1), R);
	}
	else {
		cout << "? " << L << ' ' << L + (1 << B1) << endl;
		int s; cin >> s;
		cout << "? " << R - (1 << B2) << ' ' << R << endl;
		int t; cin >> t;
		return s + t - sum(pos + 1, R - (1 << B2), L + (1 << B1));
	}
}
int main() {
	cin >> n;
	solve(n); reverse(dp[n].first.begin(), dp[n].first.end());
	cout << sum(0, 0, n) << endl;
	return 0;
}

Submission Info

Submission Time
Task A - Array Sum
User E869120
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1510 Byte
Status WA
Exec Time 88 ms
Memory 22348 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
WA × 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 WA 5 ms 3792 KB
01-02.txt WA 5 ms 3792 KB
01-03.txt WA 5 ms 3792 KB
01-04.txt WA 5 ms 3792 KB
01-05.txt WA 51 ms 14288 KB
01-06.txt WA 51 ms 14156 KB
01-07.txt WA 54 ms 14668 KB
01-08.txt WA 53 ms 14672 KB
01-09.txt WA 53 ms 14672 KB
01-10.txt WA 58 ms 15948 KB
01-11.txt WA 58 ms 15948 KB
01-12.txt WA 77 ms 19912 KB
01-13.txt WA 77 ms 19916 KB
01-14.txt WA 87 ms 22220 KB
01-15.txt WA 81 ms 20808 KB
01-16.txt WA 87 ms 22088 KB
01-17.txt WA 87 ms 22344 KB
01-18.txt WA 88 ms 22348 KB
01-19.txt WA 25 ms 8528 KB
01-20.txt WA 42 ms 12236 KB
01-21.txt WA 78 ms 20036 KB
01-22.txt WA 50 ms 14028 KB
01-23.txt WA 54 ms 14924 KB
01-24.txt WA 81 ms 20676 KB