QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735432#8553. Exchanging KubicDaiRuiChen007WA 56ms3640kbC++171.3kb2024-11-11 19:59:282024-11-11 19:59:30

Judging History

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

  • [2024-11-11 19:59:30]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:3640kb
  • [2024-11-11 19:59:28]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2005;
struct seg { int l,r; ll s; };
int n;
ll a[MAXN];
ll qry(int l,int r) {
	cout<<"? "<<l<<" "<<r<<endl;
	ll z; cin>>z; return z;
}
void solve() {
	cin>>n;
	vector <seg> p;
	for(int i=1;i<=n;++i) {
		a[i]=qry(i,i);
		if(p.size()&&(p.back().s>0)==(a[i]>0)) p.back().s+=a[i],p.back().r=i;
		else p.push_back({i,i,a[i]});
	}
	if(!p.front().s) p.erase(p.begin());
	if(!p.back().s) p.erase(--p.end());
	auto pop=[&](int l,int r) { p.erase(p.begin()+l,p.begin()+r+1); };
	while(p.size()>1) {
		int i=0;
		for(int j=0;j<(int)p.size();j+=2) if(p[j].s<p[i].s) i=j;
		if(i-2>=0) {
			ll x=qry(p[i-2].l,p[i].r);
			if(x>p[i-2].s) {
				a[p[i-1].l]=x-p[i-2].s-p[i].s;
				p[i-2].r=p[i].r,p[i-2].s=x,pop(i-1,i);
				continue;
			}
		}
		if(i+2<(int)p.size()) {
			ll x=qry(p[i].l,p[i+2].r);
			if(x>p[i+2].s) {
				a[p[i+1].l]=x-p[i+2].s-p[i].s;
				p[i+2].l=p[i].l,p[i+2].s=x,pop(i,i+1);
				continue;
			}
		}
		if(!i) a[p[i+1].l]=-p[i].s,pop(i,i+1);
		else if(i+1==(int)p.size()) a[p[i-1].r]=-p[i].s,pop(i-1,i);
		else a[p[i+1].l]=-p[i].s,p[i-1].r=p[i+1].r,pop(i,i+1);
	}
	cout<<"! "; for(int i=1;i<=n;++i) cout<<a[i]<<" "; cout<<endl;
}
signed main() {
	int T; cin>>T;
	while(T--) solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3640kb

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: 56ms
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...

result:

ok ok (10000 test cases)

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3604kb

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 120053...

result:

wrong answer mss of [1, 6] is incorrect, expected=709170957, found=770920162 (test case 11)