QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#466071 | #8553. Exchanging Kubic | zlxFTH | WA | 28ms | 3832kb | C++14 | 1.9kb | 2024-07-07 15:32:58 | 2024-07-07 15:32:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2005;
LL ask(int l, int r) {
cout << "? " << l << " " << r << endl;
LL v;
cin >> v;
return v;
}
int n;
LL a[N];
void ouf() {
cout << "!";
for (int i = 1; i <= n; ++i) cout << " " << a[i];
cout << endl;
}
struct Node {
mutable int l, r;
mutable LL v;
Node(int l, int r, LL v) : l(l), r(r), v(v) {}
bool operator<(const Node &rhs) const {
return l < rhs.l;
}
};
void solve() {
cin >> n;
fill(a + 1, a + n + 1, 0);
set<Node> s;
for (int i = 1; i <= n; ++i) {
a[i] = ask(i, i);
if (a[i] <= 0) continue;
if (i > 1 && a[i - 1] > 0) {
s.rbegin()->r = i;
s.rbegin()->v += a[i];
} else {
s.emplace(i, i, a[i]);
}
}
if (!s.size()) return ouf();
auto qs = [&](int l, int r) {
return accumulate(a + l, a + r + 1, 0ll);
};
while (s.size()) {
auto p = s.end();
for (auto it = s.begin(); it != s.end(); ++it)
if (p == s.end() || it->v < p->v) p = it;
if (p != s.begin()) {
auto i = prev(p);
auto val = ask(i->l, p->r);
if (val > i->v) {
a[p->l - 1] = val - i->v - p->v - qs(i->r + 1, p->l - 1);
Node nw(i->l, p->r, val);
s.erase(i), s.erase(p), s.insert(nw);
continue;
} else {
a[p->l - 1] = -p->v;
}
}
if (next(p) != s.end()) {
auto i = next(p);
auto val = ask(p->l, i->r);
if (val > i->v) {
a[p->r + 1] = val - i->v - p->v - qs(p->r + 1, i->l - 1);
Node nw(p->l, i->r, val);
s.erase(i), s.erase(p), s.insert(nw);
continue;
} else {
a[p->r + 1] = -p->v;
}
}
s.erase(p);
}
ouf();
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3832kb
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 -1 1 ? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 1 3 ? 1 5 ! 2 -1 3 -4 5
result:
ok ok (2 test cases)
Test #2:
score: 0
Accepted
time: 28ms
memory: 3788kb
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 ! 345108193 ? 1 1 ! ...
result:
ok ok (10000 test cases)
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3808kb
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 1112480382 1112480382 10 0 737563509 985502704 427600980 0 805973591 7...
output:
? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 6 6 ? 7 7 ? 8 8 ? 9 9 ? 1 3 ? 3 7 ! 167536100 -167536100 373372185 -373372185 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 -120053133 1200531...
result:
wrong answer mss of [1, 4] is incorrect, expected=1670744515, found=2234086166 (test case 5)