QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#473118#8553. Exchanging KubicPhantomThresholdWA 24ms3580kbC++202.4kb2024-07-11 21:58:442024-07-11 21:58:46

Judging History

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

  • [2024-07-11 21:58:46]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:3580kb
  • [2024-07-11 21:58:44]
  • 提交

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)