QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#735432 | #8553. Exchanging Kubic | DaiRuiChen007 | WA | 56ms | 3640kb | C++17 | 1.3kb | 2024-11-11 19:59:28 | 2024-11-11 19:59:30 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2005;
struct seg { int l,r; ll s; };
int n;
ll a[MAXN];
ll qry(int l,int r) {
cout<<"? "<<l<<" "<<r<<endl;
ll z; cin>>z; return z;
}
void solve() {
cin>>n;
vector <seg> p;
for(int i=1;i<=n;++i) {
a[i]=qry(i,i);
if(p.size()&&(p.back().s>0)==(a[i]>0)) p.back().s+=a[i],p.back().r=i;
else p.push_back({i,i,a[i]});
}
if(!p.front().s) p.erase(p.begin());
if(!p.back().s) p.erase(--p.end());
auto pop=[&](int l,int r) { p.erase(p.begin()+l,p.begin()+r+1); };
while(p.size()>1) {
int i=0;
for(int j=0;j<(int)p.size();j+=2) if(p[j].s<p[i].s) i=j;
if(i-2>=0) {
ll x=qry(p[i-2].l,p[i].r);
if(x>p[i-2].s) {
a[p[i-1].l]=x-p[i-2].s-p[i].s;
p[i-2].r=p[i].r,p[i-2].s=x,pop(i-1,i);
continue;
}
}
if(i+2<(int)p.size()) {
ll x=qry(p[i].l,p[i+2].r);
if(x>p[i+2].s) {
a[p[i+1].l]=x-p[i+2].s-p[i].s;
p[i+2].l=p[i].l,p[i+2].s=x,pop(i,i+1);
continue;
}
}
if(!i) a[p[i+1].l]=-p[i].s,pop(i,i+1);
else if(i+1==(int)p.size()) a[p[i-1].r]=-p[i].s,pop(i-1,i);
else a[p[i+1].l]=-p[i].s,p[i-1].r=p[i+1].r,pop(i,i+1);
}
cout<<"! "; for(int i=1;i<=n;++i) cout<<a[i]<<" "; cout<<endl;
}
signed main() {
int T; cin>>T;
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
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: 56ms
memory: 3576kb
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: -100
Wrong Answer
time: 2ms
memory: 3604kb
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 120053...
result:
wrong answer mss of [1, 6] is incorrect, expected=709170957, found=770920162 (test case 11)