Submission #1089072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089072		Izzy	JJOOII 2 (JOI20_ho_t2)	C++14	0 / 100	0 ms	348 KiB

ho_t2

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

string s;
int n; 
int k;

int counts = -1;

void test(int start, int end, unordered_map<char, int> joi, int counter) {
    if (joi['J'] < k || joi['O'] < k || joi['I'] < k) {
        return;
    }
    if (joi['J'] == k || joi['O'] == k || joi['I'] == k) {
        if (counts == -1 || counter < counts) {
            counts = counter;
        }
        return;
    }
    if (joi[s[start]] > k) {
        joi[s[start]]--;
        test(start + 1, end, joi, counter);
        joi[s[start]]++;
    }
    if (joi[s[end]] > k) {
        joi[s[end]]--;
        test(start, end - 1, joi, counter);
        joi[s[end]]++;
    }

    if (joi[s[start]] == k && joi[s[end]] == k) {
        if (s[start] != s[end]) {
            char missing;
            if ((s[start] == 'J' && s[end] == 'O') || (s[start] == 'O' && s[end] == 'J')) {
                missing = 'I';
            }
            else if ((s[start] == 'J' && s[end] == 'I') || (s[start] == 'O' && s[end] == 'I')) {
                missing = 'O';
            }
            else if ((s[start] == 'I' && s[end] == 'O') || (s[start] == 'I' && s[end] == 'J')) {
                missing = 'J';
            }
            counter += joi[missing] - k;
            if (counts == -1 || counter < counts) {
                counts = counter;
            }
            return;
        }
        else {
            char missing[2];
            if (s[start] == 'J') {
                missing[0] = 'O';
                missing[1] = 'I';
            }
            else if (s[start] == 'O') {
                missing[0] = 'I';
                missing[1] = 'J';
            }
            else if (s[start] == 'I') {
                missing[0] = 'J';
                missing[1] = 'I';
            }
            counter += joi[missing[0]] + joi[missing[1]] - k - k;
            if (counts == -1 || counter < counts) {
                counts = counter;
            }
            return;
        }
        return;
    }
    return;
}

int main() {
    cin >> n;
    cin >> k;
    cin >> s;

    int counter = 0;
    unordered_map<char, int> joi;
    joi['J'] = 0;
    joi['O'] = 0;
    joi['I'] = 0;

    for (auto p: s) {
        joi[p]++;
    }
    test(0, n - 1, joi, 0);
    cout << counter;

    
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87