QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#473298#8553. Exchanging KubicPhantomThresholdAC ✓53ms4056kbC++203.1kb2024-07-12 00:49:462024-07-12 00:49:46

Judging History

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

  • [2024-07-12 00:49:46]
  • 评测
  • 测评结果:AC
  • 用时:53ms
  • 内存:4056kb
  • [2024-07-12 00:49:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	mt19937 rng((unsigned long long)(new char));
	int T;
	cin>>T;
	while(T--)
	{
		int n=rng()%15+1;
/*		
		vector<long long> b(n+5);
		for(int i=1;i<=n;i++)
		{
			if(i%2==1)b[i]=rng()%1000000000+1;
			else b[i]=-((int)(rng()%1000000000));
			//b[i]=(int)rng()%11-5;
			cerr<<b[i]<<" \n"[i==n];
		}
		auto mss=[&](const vector<long long> &v,int l,int r)
		{
			long long s=0,m=0;
			for(int i=l;i<=r;i++)
			{
				s+=v[i];
				if(s<0)s=0;
				m=max(m,s);
			}
			return m;
		};
*/		
		map<pair<int,int>,long long> rec;
		int cnt=0;
		auto query=[&](int l,int r)
		{
			if(rec.contains({l,r}))return rec[{l,r}];
			cout<<"? "<<l<<' '<<r<<endl;
			cnt++;
			long long res;
//			res=mss(b,l,r);
			cin>>res;
			return rec[{l,r}]=res;
		};
		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(not vec.empty() and vec.back().val<=0)vec.pop_back();
		function<bool(int)> chk3=[&](int i)
		{
			if(i<0 or i+2>=(int)vec.size())return false;
//			cerr<<"chk3 "<<i<<endl;
			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);
				return true;
			}
			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;
				return false;
			}
		};
		while(vec.size()>1u)
		{
//			cerr<<"now vec :"<<endl;
//			for(auto [l,r,val]:vec)cerr<<l<<' '<<r<<' '<<val<<endl;
			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)
			{
				if(not chk3(i))
					vec.erase(vec.begin(),vec.begin()+2);
			}
			else if(i==(int)vec.size()-1)
			{
				if(not chk3(i-2))
					vec.erase(vec.end()-2,vec.end());
			}
			else
			{
				if(chk3(i-2))continue;
				if(chk3(i))continue;
				//merge
//				cerr<<"merge "<<i<<endl;
				vec[i-2].r=vec[i].r;
				vec[i-2].val+=vec[i-1].val+vec[i].val;
				vec.erase(vec.begin()+i-1,vec.begin()+i+1);
			}
		}
		cout<<"!";
		for(int i=1;i<=n;i++)
		{
			cout<<' '<<a[i];
		}
		cout<<endl;
		
		//check
		/*
		int ok=1;
		for(int l=1;l<=n;l++)
		{
			for(int r=l;r<=n;r++)
			{
				if(mss(b,l,r)!=mss(a,l,r))
				{
					cerr<<"BOOM "<<l<<' '<<r<<endl;
					ok=0;
				}
			}
		}
		assert(ok and cnt<=2*n);
		*/
	}
	
	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: 38ms
memory: 3848kb

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: 0
Accepted
time: 16ms
memory: 3780kb

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 -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
? 6 9
? 1 7
! 248442934 306962195 570791475 593033322 -80983651 582850731 559429390 -120053133 1200531...

result:

ok ok (1052 test cases)

Test #4:

score: 0
Accepted
time: 39ms
memory: 3620kb

input:

105
98
0
622130364
0
603542943
491665548
0
535594695
169182905
269002770
437838930
534070706
783210752
0
914335037
560159875
0
216552904
666995724
0
0
0
753649796
0
0
0
779352417
0
121063647
0
496743470
0
4104890
0
648149367
0
965790695
732089017
0
0
0
0
6701195
0
0
0
0
750231085
0
0
511641740
36964...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (105 test cases)

Test #5:

score: 0
Accepted
time: 28ms
memory: 3916kb

input:

10
911
0
0
318490282
367703800
0
447141340
683983129
0
319014522
385248618
0
0
0
453686281
0
0
503449442
0
451161866
0
422033116
892391115
0
0
0
0
0
0
116949378
0
305018897
441460055
390798833
643328028
0
0
785497871
0
0
0
0
702685168
0
177748037
150437291
920782161
719254975
0
519494673
555035366
0...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (10 test cases)

Test #6:

score: 0
Accepted
time: 33ms
memory: 3764kb

input:

5
1952
0
207059033
0
846665449
247683562
650126777
348616690
570194875
727419904
504212241
0
0
491140658
0
876684021
0
8207113
0
0
0
0
0
0
325502144
0
78879155
0
828506541
357830073
0
831431906
864603826
0
0
656125431
582335892
651256373
0
640787570
0
103421615
0
0
0
0
0
481682299
493673601
93577949...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (5 test cases)

Test #7:

score: 0
Accepted
time: 16ms
memory: 3956kb

input:

5
2000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (5 test cases)

Test #8:

score: 0
Accepted
time: 20ms
memory: 3872kb

input:

1052
9
911133045
0
526984535
0
931320524
0
928006811
0
176872302
928006811
1331374524
1340686664
1808307998
9
916585987
0
423565782
0
615681673
0
935399347
0
661248049
1275831339
1377399889
935399347
2278784416
10
587217915
0
129148010
0
316225345
0
935126806
0
641901481
0
587217915
316225345
587217...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 7 9
? 1 3
? 5 7
? 1 7
! 911133045 -106743056 526984535 -863753190 931320524 -518640671 928006811 -176872302 176872302
? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 1 3
? 1 5
? 7 9
? 1 7
! 916585987 -64320430 423565782 -514113123 61568...

result:

ok ok (1052 test cases)

Test #9:

score: 0
Accepted
time: 18ms
memory: 3876kb

input:

105
98
488529703
0
468492922
0
802901522
0
475641005
0
635144928
0
319324280
0
312095441
0
637285947
0
863514749
0
567178596
0
785897142
0
706104708
0
913552861
0
580235462
0
86293259
0
945400504
0
549373433
0
807677852
0
115856051
0
376484061
0
984127422
0
202884700
0
516705542
0
286842060
0
517315...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (105 test cases)

Test #10:

score: 0
Accepted
time: 47ms
memory: 3744kb

input:

10
911
190008868
0
267501671
0
615470163
0
133513401
0
314315377
0
660548519
0
555314918
0
941289689
0
231059371
0
56848945
0
294509086
0
423676574
0
947717893
0
631853488
0
420480249
0
447345907
0
368504182
0
757380250
0
498988264
0
155354017
0
832730679
0
982153581
0
779911649
0
228619121
0
524075...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (10 test cases)

Test #11:

score: 0
Accepted
time: 53ms
memory: 4056kb

input:

5
1952
270943944
0
427827622
0
706467567
0
657378898
0
336632977
0
646373280
0
330175227
0
636169757
0
614552419
0
752377204
0
964998361
0
223064174
0
402544250
0
855778411
0
374152994
0
278416329
0
988879952
0
151167996
0
775855140
0
366009963
0
63772275
0
189944036
0
123776551
0
636001304
0
860458...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (5 test cases)

Extra Test:

score: 0
Extra Test Passed