Submission #880194

# Submission time Handle Problem Language Result Execution time Memory
880194 2023-11-29T02:47:57 Z irmuun Sequence (APIO23_sequence) C++17
0 / 100
47 ms 19652 KB
#include<bits/stdc++.h>
#include "sequence.h"

using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int sequence(int N,vector<int>A){
    int mx=0;
    for(auto x:A){
        mx=max(mx,x);
    }
    if(mx<=3){
        vector<int>cnt(4,0),c1(N+1,0),c3(N+1,0);
        for(int i=0;i<N;i++){
            cnt[A[i]]++;
            c1[i+1]=c1[i]+(A[i]==1);
            c3[i+1]=c3[i]+(A[i]==3);
        }
        if(cnt[1]>=cnt[2]+cnt[3]){
            return cnt[1];
        }
        if(cnt[3]>=cnt[2]+cnt[1]){
            return cnt[3];
        }
        int cur1=0,cur3=0,mn1,mn2,ans=cnt[2];
        vector<pair<int,int>>s1,s3;
        for(int i=0;i<N;i++){
            cur1+=(A[i]==1?1:-1);
            cur3+=(A[i]==3?1:-1);
            s1.pb({cur1,i});
            s3.pb({cur3,i});
        }
        sort(all(s1));
        sort(all(s3));
        set<int>st;
        for(auto [c,i]:s1){
            st.insert(i);
            int x=*st.begin();
            ans=max(ans,c1[i+1]-c1[x]);
        }
        st.clear();
        for(auto [c,i]:s3){
            st.insert(i);
            int x=*st.begin();
            ans=max(ans,c3[i+1]-c3[x]);
        }
        return ans;
    }
}

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:31:27: warning: unused variable 'mn1' [-Wunused-variable]
   31 |         int cur1=0,cur3=0,mn1,mn2,ans=cnt[2];
      |                           ^~~
sequence.cpp:31:31: warning: unused variable 'mn2' [-Wunused-variable]
   31 |         int cur1=0,cur3=0,mn1,mn2,ans=cnt[2];
      |                               ^~~
sequence.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
   55 | }
      | ^
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 19652 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -