Submission #977910

#	Time	Username	Problem	Language	Result	Execution time	Memory
977910		Unforgettablepl	Sequence (APIO23_sequence)	C++17	12 / 100	113 ms	8528 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<>, rb_tree_tag,tree_order_statistics_node_update>

#define int long long

int32_t sequence(int32_t N, std::vector<int32_t> A) {
    int32_t ans = 0;
    auto calc = [&](int len,int curr){
        vector<int32_t> cnt(4);
        if(len>N)return false;
        for(int i=0;i<len-1;i++)cnt[A[i]]++;
        bool works = false;
        for(int i=len-1;i<N;i++){
            cnt[A[i]]++;
            if(i-len>=0)cnt[A[i-len]]--;
            int lower,upper;
            if(curr==1){
                lower = 0;
                upper = cnt[1]-1;
            } else if(curr==2){
                lower = cnt[1];
                upper = cnt[2]+cnt[1]-1;
            } else {
                lower = cnt[2]+cnt[1];
                upper = len-1;
            }
            if(len/2<=upper and lower<=len/2){
                ans = max(ans,cnt[curr]);
                works = true;
            }
            if(len%2==0 and (len/2)-1 <= upper and (len/2)-1 >= lower){
                ans = max(ans,cnt[curr]);
                works = true;
            }
        }
        return works;
    };
    for(int i=1;i<=3;i++){
        int curr = 0;
        for(int jump=262144;jump;jump/=2)if(calc(curr+jump,i))curr+=jump;
    }
    return ans;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 12 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18