Submission #1145369

#TimeUsernameProblemLanguageResultExecution timeMemory
1145369vincentbucourt1JOIOJI (JOI14_joioji)C++20
100 / 100
45 ms7236 KiB
#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long

const int MAXN = 200'020;

int N;
int scroll[MAXN];
map<pair<int,int>,int> idxDiff;
int ans = 0;

signed main() {
    fastIO();
    cin >> N;
    for (int i = 0; i < N; i++) {
        char on;
        cin >> on;
        if (on == 'J') {
            scroll[i] = 0;
        }
        else if (on == 'O') {
            scroll[i] = 1;
        }
        else {
            assert(on == 'I');
            scroll[i] = 2;
        }
    }
    vector<int> cnt(3,0);
    idxDiff[{0,0}] = -1;
    for (int i = 0; i < N; i++) {
        cnt[scroll[i]]++;
        pair<int,int> add = {cnt[0]-cnt[1], cnt[1]-cnt[2]};
        if (idxDiff.find(add) == idxDiff.end()) {
            idxDiff[add] = i;
        }
        pair<int,int> fnd = {cnt[0]-cnt[1], cnt[1]-cnt[2]};
        auto idxId = idxDiff.find(fnd);
        if (idxId != idxDiff.end()) {
            int idx = idxDiff[fnd];
            ans = max(ans, i - idx);
        }
    }
    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...