QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#401701#8553. Exchanging KubicmarherWA 16ms3692kbC++142.0kb2024-04-29 09:56:152024-04-29 09:56:15

Judging History

你现在查看的是最新测评结果

  • [2024-04-29 09:56:15]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:3692kb
  • [2024-04-29 09:56:15]
  • 提交

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)