QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#401701 | #8553. Exchanging Kubic | marher | WA | 16ms | 3692kb | C++14 | 2.0kb | 2024-04-29 09:56:15 | 2024-04-29 09:56:15 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+500,inf=1e9;
struct node
{
int l,r,w;
friend bool operator<(node a,node b)
{
return a.l<b.l;
}
};
int T,n,a[N];
set<node>s;
int ask(int l,int r)
{
cout<<"? "<<l<<' '<<r<<endl;
int ans;cin>>ans;return ans;
}
int merge(set<node>::iterator p1,set<node>::iterator p2,set<node>::iterator p3)
{
auto x=*p1,y=*p2,z=*p3;
int w=ask(x.l,z.r);
if(w==max(x.w,z.w))
{
if((p1==s.begin()&&w==z.w)||(p3==(--s.end())&&w==x.w))
{
a[y.l]=-inf;
if(p1==s.begin())s.erase(p1,p3);
else s.erase(p2,s.end());
return 1;
}
return 0;
}
a[y.l]=w-x.w-z.w;s.erase(p1,++p3);s.insert((node){x.l,z.r,w});
return 1;
}
int mergefir(set<node>::iterator pos)
{
auto p1=pos;pos++;
if(pos==s.end())return 0;
auto p2=pos,p3=++pos;
return merge(p1,p2,p3);
}
int mergelas(set<node>::iterator pos)
{
if(pos==s.begin())return 0;
auto p1=pos,p2=--pos,p3=--pos;
return merge(p3,p2,p1);
}
void sol()
{
cin>>n;
for(int i=1;i<=n;i++)a[i]=ask(i,i);
for(int i=1;i<=n;i++)
{
int pos=i,sum=0;
while(pos<=n&&(a[pos]==0)==(a[i]==0))sum+=a[pos++];
if(sum||(i>1&&pos<=n))s.insert((node){i,pos-1,sum});
i=pos-1;
}
while(s.size()>1)
{
auto pos=s.begin(),x=s.begin();
while(x!=s.end())
{
if((*x).w&&(*x).w<(*pos).w)pos=x;
++x;
}
if(mergefir(pos)||mergelas(pos))continue;
auto A=pos,B=pos;A--;B++;auto C=B;C++;
a[(*B).l]=-(*pos).w;node p=(node){(*A).l,(*B).r,0};
s.erase(A,C);s.insert(p);
}
cout<<"! ";
for(int i=1;i<=n;i++)cout<<a[i]<<' ';cout<<endl;
s.clear();
}
main()
{
// freopen("in.txt","r",stdin);
cin>>T;
while(T--)sol();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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 -1000000000 1 ? 1 1 ? 2 2 ? 3 3 ? 4 4 ? 5 5 ? 1 3 ? 1 5 ! 2 -1 3 -1000000000 5
result:
ok ok (2 test cases)
Test #2:
score: 0
Accepted
time: 16ms
memory: 3692kb
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: 4ms
memory: 3540kb
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 -1000000000 373372185 -1000000000 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 -1000000000 120...
result:
wrong answer mss of [1, 10] is incorrect, expected=1796622649, found=2164186310 (test case 30)