QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393773#8553. Exchanging KubicYMH_fourteenWA 13ms3796kbC++142.8kb2024-04-19 11:37:052024-04-19 11:37:06

Judging History

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

  • [2024-04-19 11:37:06]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:3796kb
  • [2024-04-19 11:37:05]
  • 提交

answer

// Author: Minghan Ye (Donotplaygame)
// Name: L. Exchanging Kubic
// URL: https://qoj.ac/contest/1596/problem/8553
// ML: 1024 MB
// TL: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "E:/OI/normal/templates/debug.h"
#else
#define dbg(...) (void)0
#define msg(...) (void)0
#endif
#define ll long long
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define fi first
#define se second

const int N=2005;
int n;
ll a[N],sm[N];
ll ask(int l,int r)
{
	cout<<"? "<<l<<" "<<r<<endl;
	ll res;cin>>res;
	return res;
}
void answer()
{
	cout<<"!";
	for(int i=1;i<=n;i++)cout<<" "<<a[i];
	cout<<endl;
}
void upd()
{
	for(int i=1;i<=n;i++)sm[i]=sm[i-1]+a[i];
}
ll sum(int l,int r){return sm[r]-sm[l-1];}

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
	int _;cin>>_;while(_--)
{
	cin>>n;
	for(int i=1;i<=n;i++)a[i]=ask(i,i);
	vector<PII> p;
	for(int i=1;i<=n;i++)
		if(a[i]>0)p.PB(i,i);
	for(int i=1;i<=n+1;i++)
		
	while(p.size()>1)
	{
//		cerr<<"p = [";
//		for(int i=0;i<p.size();i++)fprintf(stderr,"(%d, %d)%s",p[i].fi,p[i].se,i+1==p.size()?"]\n":", ");
		upd();
		vector<PII>::iterator it;
		for(auto i=p.begin();i!=p.end();i++)
			if(i==p.begin()||sum(i->fi,i->se)<sum(it->fi,it->se))it=i;
		if(it!=p.begin()&&(it-1)->se+1<it->fi)
		{
			ll t=ask((it-1)->fi,it->se),s=sum((it-1)->fi,(it-1)->se);
			if(t>s)
			{
				int ls=-1,rs=-1;
				for(int i=(it-1)->se+1;;i++)
				{
					if(a[i]>0)break;
					if(a[i]<0){ls=i;break;}
				}
				for(int i=it->fi-1;;i--)
				{
					if(a[i]>0)break;
					if(a[i]<0){rs=i;break;}
				}
				if(~ls)a[rs]=s-t-a[ls];
				else a[it->fi-1]=s-t;
				int st=(it-1)->fi,ed=it->se;
				p.emplace(p.erase(it-1,it+1),st,ed);
				continue;
			}
		}
		if(it+1!=p.end()&&(it+1)->fi-1>it->se)
		{
			ll t=ask(it->fi,(it+1)->se),s=sum((it+1)->fi,(it+1)->se);
			if(t>s)
			{
				int ls=-1,rs=-1;
				for(int i=it->se+1;;i++)
				{
					if(a[i]>0)break;
					if(a[i]<0){ls=i;break;}
				}
				for(int i=(it+1)->fi-1;;i--)
				{
					if(a[i]>0)break;
					if(a[i]<0){rs=i;break;}
				}
				if(~ls)a[rs]=s-t-a[ls];
				else a[it->se+1]=s-t;
				int st=it->fi,ed=(it+1)->se;
				p.emplace(p.erase(it,it+2),st,ed);
				continue;
			}
		}
		if(it!=p.begin()&&(it-1)->se+1==it->fi)
		{
			int st=(it-1)->fi,ed=it->se;
			p.emplace(p.erase(it-1,it+1),st,ed);
			continue;
		}
		if(it!=p.end()&&it->se+1==(it+1)->fi)
		{
			int st=it->fi,ed=(it+1)->se;
			p.emplace(p.erase(it,it+2),st,ed);
			continue;
		}
		a[it->fi-1]=a[it->se+1]=-sum(it->fi,it->se);
		p.erase(it);
	}
	answer();
}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 13ms
memory: 3796kb

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: 2ms
memory: 3568kb

input:

1052
9
167536100
0
373372185
0
427949326
442758705
102715118
0
0
373372185
427949326
9
248442934
306962195
570791475
593033322
0
582850731
559429390
0
120053133
559429390
1654329792

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 1 3
? 3 5
! 167536100 -373372185 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
? 7 9
? 4 7
! 248442934 306962195 570791475 593033322 -512049671 582850731 559429390 -120053133 120053...

result:

wrong answer mss of [1, 6] is incorrect, expected=2221097006, found=1790030986 (test case 2)