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 |
|
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 |