QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#401699#8553. Exchanging KubicmarherRE 9ms3660kbC++141.9kb2024-04-29 09:47:022024-04-29 09:47:03

Judging History

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

  • [2024-04-29 09:47:03]
  • 评测
  • 测评结果:RE
  • 用时:9ms
  • 内存:3660kb
  • [2024-04-29 09:47:02]
  • 提交

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()&&p3==(--s.end()))
        {
            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()
{
    cin>>T;
    while(T--)sol();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3660kb

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: 9ms
memory: 3640kb

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
Runtime Error

input:

1052
9
167536100
0
373372185
0
427949326
442758705
102715118
0
0
373372185

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 1 3

result: