Submission #968247

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
968247	2024-04-23T08:46:53 Z	Darren0724	Line Town (CCO23_day1problem3)	C++17	6 / 25	37 ms	14060 KB

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 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;
    for(int i=1;i<=n;i++){
        if(v[i]==1){
            if(st.size()&&(st.back()+i)%2==1){
                cnt+=(i-st.back());
                st.pop_back();
            } 
            else{
                st.push_back(i);
            }
        }
        if(st.size()==0){
            pre[i]=cnt;
        }
        else{
            pre[i]=INF;
        }
    }
    st.clear();
    cnt=0;
    for(int i=n;i>=1;i--){
        if(v[i]==-1){
            if(st.size()&&(st.back()+i)%2==1){
                cnt+=(st.back()-i);
                st.pop_back();
            } 
            else{
                st.push_back(i);
            }
        }
        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
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 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	0 ms	348 KB	Output is correct
6	Correct	1 ms	456 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	460 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 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	0 ms	348 KB	Output is correct
6	Correct	1 ms	456 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	460 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	37 ms	13404 KB	Output is correct
16	Correct	37 ms	13404 KB	Output is correct
17	Correct	37 ms	13392 KB	Output is correct
18	Correct	34 ms	13400 KB	Output is correct
19	Correct	34 ms	13428 KB	Output is correct
20	Correct	27 ms	14036 KB	Output is correct
21	Correct	27 ms	14040 KB	Output is correct
22	Correct	27 ms	14048 KB	Output is correct
23	Correct	27 ms	14048 KB	Output is correct
24	Correct	28 ms	14060 KB	Output is correct

Subtask #3
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 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	0 ms	348 KB	Output is correct
6	Correct	1 ms	456 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	460 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Runtime error	1 ms	604 KB	Execution killed with signal 6
15	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	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	0 ms	348 KB	Output is correct
6	Correct	1 ms	456 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	460 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	37 ms	13404 KB	Output is correct
16	Correct	37 ms	13404 KB	Output is correct
17	Correct	37 ms	13392 KB	Output is correct
18	Correct	34 ms	13400 KB	Output is correct
19	Correct	34 ms	13428 KB	Output is correct
20	Correct	27 ms	14036 KB	Output is correct
21	Correct	27 ms	14040 KB	Output is correct
22	Correct	27 ms	14048 KB	Output is correct
23	Correct	27 ms	14048 KB	Output is correct
24	Correct	28 ms	14060 KB	Output is correct
25	Runtime error	1 ms	604 KB	Execution killed with signal 6
26	Halted	0 ms	0 KB	-

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	604 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	604 KB	Execution killed with signal 6
2	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	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	0 ms	348 KB	Output is correct
6	Correct	1 ms	456 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	460 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Runtime error	1 ms	604 KB	Execution killed with signal 6
15	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	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	0 ms	348 KB	Output is correct
6	Correct	1 ms	456 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	460 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	37 ms	13404 KB	Output is correct
16	Correct	37 ms	13404 KB	Output is correct
17	Correct	37 ms	13392 KB	Output is correct
18	Correct	34 ms	13400 KB	Output is correct
19	Correct	34 ms	13428 KB	Output is correct
20	Correct	27 ms	14036 KB	Output is correct
21	Correct	27 ms	14040 KB	Output is correct
22	Correct	27 ms	14048 KB	Output is correct
23	Correct	27 ms	14048 KB	Output is correct
24	Correct	28 ms	14060 KB	Output is correct
25	Runtime error	1 ms	604 KB	Execution killed with signal 6
26	Halted	0 ms	0 KB	-

Submission #968247

Compilation message