oj.uz

Submission #968261

# Submission time Handle Problem Language Result Execution time Memory
968261 2024-04-23T09:04:45 Z Darren0724 Line Town (CCO23_day1problem3) C++17
0 / 25
 1 ms 348 KB 
#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];
    }
    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
*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -