Submission #967998

#	Time	Username	Problem	Language	Result	Execution time	Memory
967998		Darren0724	Line Town (CCO23_day1problem3)	C++17	0 / 25	1 ms	600 KiB

Main

#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 int INF=1e9;
int32_t main(){
    LCBorz;
    int n;cin>>n;
    vector<int> v(n+2),pre(n+2),suf(n+2);
    for(int i=1;i<=n;i++){
        cin>>v[i];
        assert(abs(v[i])==1);
    }
    int last=-1,cnt=0,can=1;
    for(int i=1;i<=n;i++){
        if(v[i]==1){
            if(last!=-1){
                if((last+i)%2==0)can=0;
                cnt+=(i-last);
                last=-1;
            }
            else{
                last=i;
            }    
        }
        if(can&&last==-1){
            pre[i]=cnt/2;
        }
        else{
            pre[i]=INF;
        }
    }
    last=-1,can=1,cnt=0;
    for(int i=n;i>=1;i--){
        if(v[i]==1){
            if((last+i)%2==0){
                can=0;
            }
            if(last!=-1){
                if((last+i)%2==0)can=0;
                cnt+=(last-i);
                last=-1;
            }
            else{
                last=i;
            }    
        }
        if(can&&last==-1){
            suf[i]=cnt/2;
        }
        else{
            suf[i]=INF;
        }
    }
    int 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
• Subtask 2: 0 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 3
• Subtask 7: 0 / 2
• Subtask 8: 0 / 3