第12回日本情報オリンピック 本選(オンライン)

Submission #1440781

Source codeソースコード

#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

Task問題 4 - JOIOIの塔 (Tower of JOIOI)
User nameユーザ名 tatsukawa
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1281 Byte
File nameファイル名
Exec time実行時間 157 ms
Memory usageメモリ使用量 1280 KB

Test case

Set

Set name Score得点 / Max score Cases
01 10 / 10 01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt
02 20 / 20 02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt
03 20 / 20 03-01.txt,03-02.txt,03-03.txt,03-04.txt,03-05.txt,03-06.txt,03-07.txt,03-08.txt,03-09.txt,03-10.txt
04 30 / 30 04-01.txt,04-02.txt,04-03.txt,04-04.txt,04-05.txt,04-06.txt,04-07.txt,04-08.txt,04-09.txt,04-10.txt
05 20 / 20 05-01.txt,05-02.txt,05-03.txt,05-04.txt,05-05.txt,05-06.txt,05-07.txt,05-08.txt,05-09.txt,05-10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 1 ms 256 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 1 ms 256 KB
01-07.txt AC 1 ms 256 KB
01-08.txt AC 1 ms 256 KB
01-09.txt AC 1 ms 256 KB
01-10.txt AC 1 ms 256 KB
02-01.txt AC 1 ms 256 KB
02-02.txt AC 1 ms 256 KB
02-03.txt AC 1 ms 256 KB
02-04.txt AC 1 ms 256 KB
02-05.txt AC 1 ms 256 KB
02-06.txt AC 1 ms 256 KB
02-07.txt AC 1 ms 256 KB
02-08.txt AC 1 ms 256 KB
02-09.txt AC 1 ms 256 KB
02-10.txt AC 1 ms 256 KB
03-01.txt AC 1 ms 256 KB
03-02.txt AC 1 ms 256 KB
03-03.txt AC 1 ms 256 KB
03-04.txt AC 1 ms 256 KB
03-05.txt AC 1 ms 256 KB
03-06.txt AC 1 ms 256 KB
03-07.txt AC 1 ms 256 KB
03-08.txt AC 1 ms 256 KB
03-09.txt AC 1 ms 256 KB
03-10.txt AC 1 ms 256 KB
04-01.txt AC 10 ms 384 KB
04-02.txt AC 10 ms 384 KB
04-03.txt AC 10 ms 384 KB
04-04.txt AC 10 ms 384 KB
04-05.txt AC 9 ms 384 KB
04-06.txt AC 14 ms 384 KB
04-07.txt AC 14 ms 384 KB
04-08.txt AC 14 ms 384 KB
04-09.txt AC 14 ms 384 KB
04-10.txt AC 14 ms 384 KB
05-01.txt AC 151 ms 1280 KB
05-02.txt AC 151 ms 1280 KB
05-03.txt AC 145 ms 1280 KB
05-04.txt AC 157 ms 1280 KB
05-05.txt AC 145 ms 1280 KB
05-06.txt AC 127 ms 1280 KB
05-07.txt AC 127 ms 1280 KB
05-08.txt AC 127 ms 1280 KB
05-09.txt AC 122 ms 1280 KB
05-10.txt AC 122 ms 1280 KB