#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define ll long long
#define LCBorz ios_base::sync_with_stdio(false);cin.tie(0);
const int N=1000005;
const int mod=1e6+3;
const ll INF=1e18;
int32_t main(){
LCBorz;
int n;cin>>n;
vector<ll> v(n+2),pre(n+2),suf(n+2);
for(int i=1;i<=n;i++){
cin>>v[i];
assert(abs(v[i])<=1);
}
ll cnt=0;
vector<int> st;
int lz=0,zero=0,id=0;
for(int i=1;i<=n;i++){
if(v[i]==0){
lz^=1;
zero++;
}
else {
id++;
cnt+=zero;
if((v[i]==1)^lz){
if(st.size()&&(st.back()+id)%2==1){
cnt+=(id-st.back());
st.pop_back();
}
else{
st.push_back(id);
}
}
}
if(st.size()==0){
pre[i]=cnt;
}
else{
pre[i]=INF;
}
}
st.clear();
cnt=0;
lz=0;
zero=0;
id=0;
for(int i=n;i>=1;i--){
if(v[i]==0){
lz^=1;
zero++;
}
else {
id++;
cnt+=zero;
if((v[i]==-1)^lz){
if(st.size()&&(st.back()+id)%2==1){
cnt+=(id-st.back());
st.pop_back();
}
else{
st.push_back(id);
}
}
}
if(st.size()==0){
suf[i]=cnt;
}
else{
suf[i]=INF;
}
}
ll ans=INF;
for(int i=0;i<=n;i++){
ans=min(ans,pre[i]+suf[i+1]);
//cout<<pre[i]<<' '<<suf[i+1]<<endl;
}
if(ans==INF){
cout<<-1<<endl;
}
else{
cout<<ans<<endl;
}
return 0;
}
/*
20
1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 -1 1
4
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
33 ms |
12220 KB |
Output is correct |
16 |
Correct |
39 ms |
12120 KB |
Output is correct |
17 |
Correct |
39 ms |
12124 KB |
Output is correct |
18 |
Correct |
33 ms |
12120 KB |
Output is correct |
19 |
Correct |
34 ms |
12120 KB |
Output is correct |
20 |
Correct |
28 ms |
12592 KB |
Output is correct |
21 |
Correct |
27 ms |
12760 KB |
Output is correct |
22 |
Correct |
27 ms |
12768 KB |
Output is correct |
23 |
Correct |
28 ms |
12756 KB |
Output is correct |
24 |
Correct |
27 ms |
12756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
33 ms |
12220 KB |
Output is correct |
16 |
Correct |
39 ms |
12120 KB |
Output is correct |
17 |
Correct |
39 ms |
12124 KB |
Output is correct |
18 |
Correct |
33 ms |
12120 KB |
Output is correct |
19 |
Correct |
34 ms |
12120 KB |
Output is correct |
20 |
Correct |
28 ms |
12592 KB |
Output is correct |
21 |
Correct |
27 ms |
12760 KB |
Output is correct |
22 |
Correct |
27 ms |
12768 KB |
Output is correct |
23 |
Correct |
28 ms |
12756 KB |
Output is correct |
24 |
Correct |
27 ms |
12756 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
33 ms |
12220 KB |
Output is correct |
16 |
Correct |
39 ms |
12120 KB |
Output is correct |
17 |
Correct |
39 ms |
12124 KB |
Output is correct |
18 |
Correct |
33 ms |
12120 KB |
Output is correct |
19 |
Correct |
34 ms |
12120 KB |
Output is correct |
20 |
Correct |
28 ms |
12592 KB |
Output is correct |
21 |
Correct |
27 ms |
12760 KB |
Output is correct |
22 |
Correct |
27 ms |
12768 KB |
Output is correct |
23 |
Correct |
28 ms |
12756 KB |
Output is correct |
24 |
Correct |
27 ms |
12756 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
27 |
Halted |
0 ms |
0 KB |
- |