Submission #1440781

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int N;
char S[1000001];

// 右側のIの数がn個のときJOIOIの塔を完成することは可能か？
bool check(int n) {
    int I = 0, O = 0;
    int cnt = 0, x = 0;
    for(int i = N-1; i >= 0; i--) {
        if(S[i] == 'J') {
            if(O > 0) {
                cnt++;
                O--;
            }
        } 
        
        if(S[i] == 'O') {
            if(I > 0) {
                O++;
                I--;
            }
        }

        if(S[i] == 'I') {
            if(x == n) {
                if(O > 0) {
                    cnt++;
                    O--;
                }
            }
            else {
                I++;
                x++;
            }
        }
    }
//    cout << cnt << ':' << n << endl;

    return (n == cnt ? true : false);
}

int main() {
    cin >> N >> S;

    int l = 0;
    int r = N/3 + 1;
    while(l+1 < r) {
        int m = (l+r)/2;
//        cout << m << ':' << check(m) << endl;

        if(check(m)) {
            l = m;
        } else {
            r = m-1;
        }
    }

    int ans = -1;
    if(check(l)) ans = max(ans, l);
    if(check(r)) ans = max(ans, r);

    cout << ans << endl;
}

Submission Info

Judge Result