QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#593471 | #9142. Uniting Amoebas | kongksora# | WA | 55ms | 7896kb | C++14 | 1.1kb | 2024-09-27 14:16:12 | 2024-09-27 14:16:13 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long ll;
const int N = 4e5;
int pre[N + 5], nxt[N + 5];
ll a[N + 5];
typedef std::pair<ll, int> pii;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
ll ans = 0;
scanf("%d", &n);
std::set<pii> st;
for (int i = 1; i <= n; i++) {
pre[i] = i == 1 ? n : i - 1;
nxt[i] = i == n ? 1 : i + 1;
scanf("%lld", &a[i]);
st.insert({a[i], i});
}
for (int _ = 1; _ < n; _++) {
auto u = st.begin();
int idx = u->second;
int mi;
if (a[pre[idx]] < a[nxt[idx]]) {
mi = nxt[idx];
pre[mi] = pre[idx];
} else {
mi = pre[idx];
nxt[mi] = nxt[idx];
}
st.erase({a[idx], idx});
st.erase({a[mi], mi});
ans += a[idx];
a[mi] += a[idx];
st.insert({a[mi], mi});
}
printf("%lld\n", ans);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7804kb
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: 36ms
memory: 7896kb
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: 55ms
memory: 5848kb
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:
7527984552 8442667394 3892421924 360702696 25765648300 2530764800 7851560419 42343649379 20338326708 4888154961 3167867997 3933093899 12026142043 9318738264 6778024812 19027150836 3175593379 5671671433 8038770746 3749436788 17485820722 7999134848 13229110986 1531237380 1155994053 4307833046 71665080...
result:
wrong answer 1st numbers differ - expected: '6125364442', found: '7527984552'