QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#473118 | #8553. Exchanging Kubic | PhantomThreshold | WA | 24ms | 3580kb | C++20 | 2.4kb | 2024-07-11 21:58:44 | 2024-07-11 21:58:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
auto query=[&](int l,int r)
{
cout<<"? "<<l<<' '<<r<<endl;
long long res;
cin>>res;
return res;
};
int n;
cin>>n;
vector<long long> a(n+5);
for(int i=1;i<=n;i++)
{
a[i]=query(i,i);
}
struct element
{
int l,r;
long long val;
};
vector<element> vec;
int pre=1;
long long sum=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]>0)
{
if(sum==0)
{
vec.emplace_back(pre,i-1,sum);
pre=i;
sum=a[i];
}
else
{
sum+=a[i];
}
}
else
{
if(sum>0)
{
vec.emplace_back(pre,i-1,sum);
pre=i;
sum=a[i];
}
else
{
sum+=a[i];
}
}
}
vec.emplace_back(pre,n,sum);
if(vec.front().val<=0)vec.erase(vec.begin());
if(vec.back().val<=0)vec.pop_back();
for(int i=0;i+2<(int)vec.size();i+=2)
{
long long res=query(vec[i].l,vec[i+2].r);
if(res>max(vec[i].val,vec[i+2].val))
{
long long newval=res-vec[i].val-vec[i+2].val;
a[vec[i+1].r]+=newval-vec[i+1].val;
//merge
vec[i].r=vec[i+2].r;
vec[i].val=res;
vec.erase(vec.begin()+i+1,vec.begin()+i+3);
i-=2;
}
else
{
long long newval=-min(vec[i].val,vec[i+2].val);
a[vec[i+1].r]+=newval-vec[i+1].val;
vec[i+1].val=newval;
}
}
while(vec.size()>1u)
{
int minpos=0;
for(int i=0;i<(int)vec.size();i+=2)
{
if(vec[i].val<vec[minpos].val)
{
minpos=i;
}
}
int i=minpos;
if(i==0)vec.erase(vec.begin(),vec.begin()+2);
else if(i==(int)vec.size()-1)vec.erase(vec.end()-2,vec.end());
else
{
long long res=query(vec[i-2].l,vec[i+2].r);
if(res>max(vec[i-2].val,vec[i+2].val))
{
long long newval=res-vec[i-2].val-vec[i-1].val-vec[i].val-vec[i+2].val;
a[vec[i+1].r]+=newval-vec[i+1].val;
//merge
vec[i-2].r=vec[i+2].r;
vec[i-2].val=res;
vec.erase(vec.begin()+i-1,vec.begin()+i+3);
}
else
{
long long newval=-(min(vec[i-2].val,vec[i+2].val)+vec[i].val);
a[vec[i+1].r]+=newval-vec[i-1].val-vec[i+1].val;
//merge
vec[i-1].val=newval+vec[i].val;
vec[i-1].r=vec[i+1].r;
vec.erase(vec.begin()+i,vec.begin()+i+2);
}
}
}
cout<<"!";
for(int i=1;i<=n;i++)
{
cout<<' '<<a[i];
}
cout<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
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: 24ms
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 ! 345108193 ? 1 1 ! ...
result:
ok ok (10000 test cases)
Test #3:
score: -100
Wrong Answer
time: 3ms
memory: 3520kb
input:
1052 9 167536100 0 373372185 0 427949326 442758705 102715118 0 0 373372185 973423149 9 248442934 306962195 570791475 593033322 0 582850731 559429390 0 120053133 2780526396 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 -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 ? 1 7 ? 1 9 ! 248442934 306962195 570791475 593033322 -80983651 582850731 559429390 -120053133 1200531...
result:
wrong answer mss of [1, 8] is incorrect, expected=2181765745, found=2350287189 (test case 5)