Submission #823736

#	Time	Username	Problem	Language	Result	Execution time	Memory
823736		hmm789	Sequence (APIO23_sequence)	C++17	12 / 100	65 ms	23084 KiB

sequence

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

int sequence(int N, std::vector<int> A) {
    #define int long long
    int c1[N+1], c2[N+1], c3[N+1], ans = 0;
    c1[0] = c2[0] = c3[0] = 0;
    for(int i = 0; i < N; i++) {
        if(A[i] == 1) c1[i+1] = c1[i]+1, c2[i+1] = c2[i], c3[i+1] = c3[i];
        if(A[i] == 2) c1[i+1] = c1[i], c2[i+1] = c2[i]+1, c3[i+1] = c3[i];
        if(A[i] == 3) c1[i+1] = c1[i], c2[i+1] = c2[i], c3[i+1] = c3[i]+1;
    }
    for(int i = 1; i <= 3; i++) {
        vector<int> idx;
        for(int j = 0; j < N; j++) if(A[j] == i) idx.push_back(j);
        int l = 1, r = idx.size()+1, m;
        while(l < r) {
            m = (l+r)/2;
            bool f = false;
            for(int j = 0; j < idx.size()-m+1; j++) {
                int below = 0, above = 0;
                if(i == 1) above = c2[idx[j+m-1]+1]-c2[idx[j]] + c3[idx[j+m-1]+1]-c3[idx[j]];
                if(i == 2) {
                    above = c3[idx[j+m-1]+1]-c3[idx[j]];
                    below = c1[idx[j+m-1]+1]-c1[idx[j]];
                }
                if(i == 3) below = c1[idx[j+m-1]+1]-c1[idx[j]] + c2[idx[j+m-1]+1]-c2[idx[j]];
                int len = idx[j+m-1]-idx[j]+1;
                if(below <= len/2 && above <= len/2 && below+above < len) f = true;
            }
            if(f) l = m+1;
            else r = m;
        }
        ans = max(ans, l-1);
    }
    return ans;
    #undef int
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:21:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   21 |             for(int j = 0; j < idx.size()-m+1; j++) {
      |                            ~~^~~~~~~~~~~~~~~~

• 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