QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#600138#9142. Uniting AmoebasANIG#WA 63ms3780kbC++141.3kb2024-09-29 14:57:572024-09-29 14:57:58

Judging History

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

  • [2024-09-29 14:57:58]
  • 评测
  • 测评结果:WA
  • 用时:63ms
  • 内存:3780kb
  • [2024-09-29 14:57:57]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
using E=long long;

void solve(){
	int n;
	cin>>n;
	priority_queue<pair<E,int>,vector<pair<E,int>>,greater<>> pq;
	multiset<pair<int,E>> st;
	for(int i=0; i<n; i++){
		int x;
		cin>>x;
		st.insert(make_pair(i,x));
		pq.push(make_pair(x,i));
	}
	
	E ans=0;
	vector<int> stt(n+1);
	while(st.size()>1){
		int u=pq.top().second;
		int v=pq.top().first;
		pq.pop();
		if(stt[u]) continue;
		auto pnt=st.lower_bound(make_pair(u,0));
		if(pnt->second!=v) continue;
		//cerr<<u<<' '<<pnt->second<<' '<<pnt->first<<endl;
		auto pnt1=(pnt==st.begin()?prev(st.end()):prev(pnt));
		auto pnt2=(next(pnt)==st.end()?st.begin():next(pnt));
		ans+=pnt->second;
		if(pnt1->second>pnt2->second){
			st.insert(make_pair(pnt1->first,pnt1->second+pnt->second));
			pq.push(make_pair(pnt1->second+pnt->second,pnt1->first));
			stt[pnt->first]=1;
			st.erase(pnt1);
			st.erase(pnt);
		}
		else{
			st.insert(make_pair(pnt2->first,pnt2->second+pnt->second));
			pq.push(make_pair(pnt2->second+pnt->second,pnt2->first));
			stt[pnt->first]=1;
			st.erase(pnt2);
			st.erase(pnt);
		}
	}
	
	cout<<ans<<'\n';
}

signed main(){
	
	cin.tie(0),cout.tie(0)->sync_with_stdio(false);
	
	int T;
	cin>>T;
	while(T--) solve();
	
	return 0;
}

詳細信息

Test #1:

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

input:

3
3
1 1 1
4
0 1 0 2
2
100 42

output:

2
1
42

result:

ok 3 number(s): "2 1 42"

Test #2:

score: 0
Accepted
time: 38ms
memory: 3636kb

input:

100000
2
653035426 456936267
2
409660907 250295986
2
347384960 200356123
2
283557883 840123319
2
17610671 987402881
2
136895857 909667348
2
248911778 780375903
2
275329617 285342631
2
561813712 698064200
2
400903421 742043963
2
345893112 519641162
2
14593307 406479738
2
616391850 347632216
2
1973087...

output:

456936267
250295986
200356123
283557883
17610671
136895857
248911778
275329617
561813712
400903421
345893112
14593307
347632216
19730879
421626272
56181583
370600905
308183211
258362299
586922640
40159075
198139063
142754581
51756812
119730671
81065481
143568225
273158312
49357396
14434997
396080587...

result:

ok 100000 numbers

Test #3:

score: -100
Wrong Answer
time: 63ms
memory: 3680kb

input:

10000
17
682602980 427465994 308629394 109001734 104676154 428796022 186854021 449599165 926341494 518520271 848737248 161898549 472666174 717817465 55045664 497142577 155911030
17
175921543 574867131 81827354 668974927 924162354 915237015 544633396 979579177 69438027 7405300 106382140 464417239 180...

output:

8497294421
10226581779
3665727762
360702696
38158662641
2673300901
8183644808
70903083908
26134709080
4932530191
3126903129
4637672178
16054108564
9142803692
6331103464
28185445928
2906086166
5962435688
11084812077
2751092954
25146147229
8465229998
14141187778
1426082634
1155994053
4065348734
874531...

result:

wrong answer 1st numbers differ - expected: '6125364442', found: '8497294421'