QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#600153 | #9142. Uniting Amoebas | ANIG# | WA | 60ms | 3832kb | C++14 | 1.3kb | 2024-09-29 15:02:11 | 2024-09-29 15:02:20 |
Judging History
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||pnt->first!=u) 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3468kb
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: 37ms
memory: 3832kb
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: 60ms
memory: 3800kb
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'