QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#388640 | #8553. Exchanging Kubic | ucup-team1198# | AC ✓ | 34ms | 3896kb | C++20 | 5.0kb | 2024-04-13 17:46:40 | 2024-04-13 17:46:40 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define int long long
const int inf = 1e15;
int n;
vector<int> a_test;
void gen_test() {
n = rand() % 50 + 1;
a_test.resize(n);
for (int i = 0; i < n; ++i) {
a_test[i] = rand() % 100 - 50;
}
}
int get(int l, int r, vector<int>& a) {
int res = 0;
for (int i = l; i < r; ++i) {
int sum = 0;
for (int j = i; j < r; ++j) {
sum += a[j];
res = max(res, sum);
}
}
return res;
}
int ask(int l, int r) {
// return get(l, r, a_test);
cout << "? " << l + 1 << ' ' << r << endl;
int res;
cin >> res;
return res;
}
struct Block {
int l;
int r;
int sum;
};
void check(vector<int> ans) {
// cerr << "check:\n";
// cerr << "give = ";
// for (int i : ans) cerr << i << ' ';
// cerr << '\n';
// cerr << "need = ";
// for (int i : a_test) cerr << i << ' ';
// cerr << '\n';
// for (int l = 0; l < n; ++l) {
// for (int r = l + 1; r <= n; ++r) {
// assert(get(l, r, ans) == get(l, r, a_test));
// }
// }
cout << "! ";
for (int i = 0; i < n; ++i) {
cout << ans[i] << ' ';
}
cout << endl;
}
void solve() {
gen_test();
cin >> n;
vector<Block> b;
vector<int> ans(n, 0);
for (int i = 0; i < n; ++i) {
ans[i] = ask(i, i + 1);
if (ans[i] > 0) {
int s = ans[i];
for (int j = i + 1; j <= n; ++j) {
if (j != n) ans[j] = ask(j, j + 1);
if (j == n || ans[j] == 0) {
// stop
b.push_back(Block{i, j, s});
i = j;
break;
} else {
s += ans[j];
}
}
} else {
continue;
}
}
while (b.size() >= 2) {
// cerr << "blocks:\n";
// for (auto bb : b) {
// cerr << bb.l << ' ' << bb.r << ' ' << bb.sum << ", ";
// }
// cerr << '\n';
if (b[0].sum <= b[1].sum) {
int r = ask(b[0].l, b[1].r);
if (r == b[1].sum) {
ans[b[0].r] = -inf;
b.erase(b.begin());
} else {
ans[b[0].r] = - (b[0].sum + b[1].sum - r);
auto l0 = b[0].l;
auto r1 = b[1].r;
b.erase(b.begin(), b.begin() + 2);
b.insert(b.begin(), Block(l0, r1, r));
}
} else if (b[b.size() - 1].sum <= b[b.size() - 2].sum) {
int r = ask(b[b.size() - 2].l, b[b.size() - 1].r);
if (r == b[b.size() - 2].sum) {
ans[b[b.size() - 2].r] = -inf;
b.erase(--b.end());
} else {
ans[b[b.size() - 2].r] = - (b[b.size() - 2].sum + b[b.size() - 1].sum - r);
auto l0 = b[b.size() - 2].l;
auto r1 = b[b.size() - 1].r;
b.pop_back();
b.pop_back();
b.insert(b.end(), Block(l0, r1, r));
}
} else {
for (int i = 0; i + 2 < b.size(); ++i) {
if (b[i].sum >= b[i + 1].sum && b[i + 1].sum <= b[i + 2].sum) {
int rl = ask(b[i].l, b[i + 1].r);
if (rl == b[i].sum) {
int rr = ask(b[i + 1].l, b[i + 2].r);
if (rr == b[i + 2].sum) {
// hmm
ans[b[i + 1].r] = -b[i + 1].sum;
b.erase(b.begin() + i + 1);
} else {
ans[b[i + 1].r] = -(b[i + 1].sum + b[i + 2].sum - rr);
auto l0 = b[i + 1].l;
auto r1 = b[i + 2].r;
b.erase(b.begin() + i + 1, b.begin() + i + 3);
b.insert(b.begin() + i + 1, Block(l0, r1, rr));
}
} else {
ans[b[i].r] = -(b[i].sum + b[i + 1].sum - rl);
auto l0 = b[i].l;
auto r1 = b[i + 1].r;
b.erase(b.begin() + i, b.begin() + i + 2);
b.insert(b.begin() + i, Block(l0, r1, rl));
}
break;
}
}
}
}
check(ans);
// cerr << "ok\n\n\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 10000;
cin >> t;
while (t--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
input:
2 3 1 0 1 1 5 2 0 3 0 5 4 5
output:
? 1 1 ? 2 2 ? 3 3 ? 1 3 ! 1 -1000000000000000 1 ? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 1 3 ? 1 5 ! 2 -1 3 -1000000000000000 5
result:
ok ok (2 test cases)
Test #2:
score: 0
Accepted
time: 9ms
memory: 3632kb
input:
10000 1 718876398 1 0 1 0 1 0 1 938356223 1 857157125 1 0 1 0 1 0 1 0 1 0 1 965894497 1 0 1 626061677 1 642094813 1 107398046 1 0 1 0 1 0 1 287188651 1 0 1 345108193 1 0 1 0 1 714952783 1 0 1 325760098 1 0 1 800487422 1 322806679 1 0 1 0 1 0 1 866952779 1 741483102 1 492063609 1 0 1 833448280 1 0 1 ...
output:
? 1 1 ! 718876398 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 938356223 ? 1 1 ! 857157125 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 965894497 ? 1 1 ! 0 ? 1 1 ! 626061677 ? 1 1 ! 642094813 ? 1 1 ! 107398046 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 0 ? 1 1 ! 287188651 ? 1 1 ! 0 ? 1 1...
result:
ok ok (10000 test cases)
Test #3:
score: 0
Accepted
time: 4ms
memory: 3796kb
input:
1052 9 167536100 0 373372185 0 427949326 442758705 102715118 0 0 373372185 973423149 9 248442934 306962195 570791475 593033322 0 582850731 559429390 0 120053133 1142280121 2780526396 10 785691778 0 981032824 0 0 592503870 0 0 0 0 981032824 1112480382 10 0 737563509 985502704 427600980 0 805973591 77...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 1 3 ? 3 7 ! 167536100 -1000000000000000 373372185 -1000000000000000 427949326 442758705 102715118 0 0 ? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 6 9 ? 1 7 ! 248442934 306962195 570791475 593033322 -80983651 582850731 559429390 -10...
result:
ok ok (1052 test cases)
Test #4:
score: 0
Accepted
time: 17ms
memory: 3880kb
input:
105 98 0 622130364 0 603542943 491665548 0 535594695 169182905 269002770 437838930 534070706 783210752 0 914335037 560159875 0 216552904 666995724 0 0 0 753649796 0 0 0 779352417 0 121063647 0 496743470 0 4104890 0 648149367 0 965790695 732089017 0 0 0 0 6701195 0 0 0 0 750231085 0 0 511641740 36964...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 10 10 ? 11 11 ? 12 12 ? 13 13 ? 14 14 ? 15 15 ? 16 16 ? 17 17 ? 18 18 ? 19 19 ? 20 20 ? 21 21 ? 22 22 ? 23 23 ? 24 24 ? 25 25 ? 26 26 ? 27 27 ? 28 28 ? 29 29 ? 30 30 ? 31 31 ? 32 32 ? 33 33 ? 34 34 ? 35 35 ? 36 36 ? 37 37 ? 38 38 ? 39 39 ? 40 4...
result:
ok ok (105 test cases)
Test #5:
score: 0
Accepted
time: 4ms
memory: 3824kb
input:
10 911 0 0 318490282 367703800 0 447141340 683983129 0 319014522 385248618 0 0 0 453686281 0 0 503449442 0 451161866 0 422033116 892391115 0 0 0 0 0 0 116949378 0 305018897 441460055 390798833 643328028 0 0 785497871 0 0 0 0 702685168 0 177748037 150437291 920782161 719254975 0 519494673 555035366 0...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 10 10 ? 11 11 ? 12 12 ? 13 13 ? 14 14 ? 15 15 ? 16 16 ? 17 17 ? 18 18 ? 19 19 ? 20 20 ? 21 21 ? 22 22 ? 23 23 ? 24 24 ? 25 25 ? 26 26 ? 27 27 ? 28 28 ? 29 29 ? 30 30 ? 31 31 ? 32 32 ? 33 33 ? 34 34 ? 35 35 ? 36 36 ? 37 37 ? 38 38 ? 39 39 ? 40 4...
result:
ok ok (10 test cases)
Test #6:
score: 0
Accepted
time: 11ms
memory: 3884kb
input:
5 1952 0 207059033 0 846665449 247683562 650126777 348616690 570194875 727419904 504212241 0 0 491140658 0 876684021 0 8207113 0 0 0 0 0 0 325502144 0 78879155 0 828506541 357830073 0 831431906 864603826 0 0 656125431 582335892 651256373 0 640787570 0 103421615 0 0 0 0 0 481682299 493673601 93577949...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 10 10 ? 11 11 ? 12 12 ? 13 13 ? 14 14 ? 15 15 ? 16 16 ? 17 17 ? 18 18 ? 19 19 ? 20 20 ? 21 21 ? 22 22 ? 23 23 ? 24 24 ? 25 25 ? 26 26 ? 27 27 ? 28 28 ? 29 29 ? 30 30 ? 31 31 ? 32 32 ? 33 33 ? 34 34 ? 35 35 ? 36 36 ? 37 37 ? 38 38 ? 39 39 ? 40 4...
result:
ok ok (5 test cases)
Test #7:
score: 0
Accepted
time: 22ms
memory: 3708kb
input:
5 2000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 10 10 ? 11 11 ? 12 12 ? 13 13 ? 14 14 ? 15 15 ? 16 16 ? 17 17 ? 18 18 ? 19 19 ? 20 20 ? 21 21 ? 22 22 ? 23 23 ? 24 24 ? 25 25 ? 26 26 ? 27 27 ? 28 28 ? 29 29 ? 30 30 ? 31 31 ? 32 32 ? 33 33 ? 34 34 ? 35 35 ? 36 36 ? 37 37 ? 38 38 ? 39 39 ? 40 4...
result:
ok ok (5 test cases)
Test #8:
score: 0
Accepted
time: 10ms
memory: 3860kb
input:
1052 9 911133045 0 526984535 0 931320524 0 928006811 0 176872302 928006811 1340686664 1331374524 1808307998 9 916585987 0 423565782 0 615681673 0 935399347 0 661248049 935399347 1275831339 1377399889 2278784416 10 587217915 0 129148010 0 316225345 0 935126806 0 641901481 0 935126806 587217915 316225...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 7 9 ? 5 7 ? 1 3 ? 1 7 ! 911133045 -106743056 526984535 -863753190 931320524 -518640671 928006811 -1000000000000000 176872302 ? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 7 9 ? 1 3 ? 1 5 ? 1 7 ! 916585987 -64320430 423565782 -5141131...
result:
ok ok (1052 test cases)
Test #9:
score: 0
Accepted
time: 25ms
memory: 3644kb
input:
105 98 488529703 0 468492922 0 802901522 0 475641005 0 635144928 0 319324280 0 312095441 0 637285947 0 863514749 0 567178596 0 785897142 0 706104708 0 913552861 0 580235462 0 86293259 0 945400504 0 549373433 0 807677852 0 115856051 0 376484061 0 984127422 0 202884700 0 516705542 0 286842060 0 517315...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 10 10 ? 11 11 ? 12 12 ? 13 13 ? 14 14 ? 15 15 ? 16 16 ? 17 17 ? 18 18 ? 19 19 ? 20 20 ? 21 21 ? 22 22 ? 23 23 ? 24 24 ? 25 25 ? 26 26 ? 27 27 ? 28 28 ? 29 29 ? 30 30 ? 31 31 ? 32 32 ? 33 33 ? 34 34 ? 35 35 ? 36 36 ? 37 37 ? 38 38 ? 39 39 ? 40 4...
result:
ok ok (105 test cases)
Test #10:
score: 0
Accepted
time: 13ms
memory: 3896kb
input:
10 911 190008868 0 267501671 0 615470163 0 133513401 0 314315377 0 660548519 0 555314918 0 941289689 0 231059371 0 56848945 0 294509086 0 423676574 0 947717893 0 631853488 0 420480249 0 447345907 0 368504182 0 757380250 0 498988264 0 155354017 0 832730679 0 982153581 0 779911649 0 228619121 0 524075...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 10 10 ? 11 11 ? 12 12 ? 13 13 ? 14 14 ? 15 15 ? 16 16 ? 17 17 ? 18 18 ? 19 19 ? 20 20 ? 21 21 ? 22 22 ? 23 23 ? 24 24 ? 25 25 ? 26 26 ? 27 27 ? 28 28 ? 29 29 ? 30 30 ? 31 31 ? 32 32 ? 33 33 ? 34 34 ? 35 35 ? 36 36 ? 37 37 ? 38 38 ? 39 39 ? 40 4...
result:
ok ok (10 test cases)
Test #11:
score: 0
Accepted
time: 34ms
memory: 3880kb
input:
5 1952 270943944 0 427827622 0 706467567 0 657378898 0 336632977 0 646373280 0 330175227 0 636169757 0 614552419 0 752377204 0 964998361 0 223064174 0 402544250 0 855778411 0 374152994 0 278416329 0 988879952 0 151167996 0 775855140 0 366009963 0 63772275 0 189944036 0 123776551 0 636001304 0 860458...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 10 10 ? 11 11 ? 12 12 ? 13 13 ? 14 14 ? 15 15 ? 16 16 ? 17 17 ? 18 18 ? 19 19 ? 20 20 ? 21 21 ? 22 22 ? 23 23 ? 24 24 ? 25 25 ? 26 26 ? 27 27 ? 28 28 ? 29 29 ? 30 30 ? 31 31 ? 32 32 ? 33 33 ? 34 34 ? 35 35 ? 36 36 ? 37 37 ? 38 38 ? 39 39 ? 40 4...
result:
ok ok (5 test cases)
Extra Test:
score: 0
Extra Test Passed