oj.uz

Submission #1089082

# Submission time Handle Problem Language Result Execution time Memory
1089082 2024-09-15T22:41:03 Z Izzy JJOOII 2 (JOI20_ho_t2) C++14
0 / 100
 0 ms 436 KB 
#include <iostream>
#include <string>
#include <vector>
// #include <unordered_map>
using namespace std;

string s;
int n; 
int k;

int find(int target, int low, vector<int> &arr) {
    int high = n;
    int working = -1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;
        if (arr[mid] >= target) {
            working = mid;
            high = mid - 1;
        } 
        else if (arr[mid] < target) {
            low = mid + 1;
        }
    }
    return working;
}

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

    vector<int> jPref = {0};
    vector<int> oPref = {0};
    vector<int> iPref = {0};

    int jCount = 0;
    int oCount = 0;
    int iCount = 0;
    for (auto p: s) {
        if (p == 'J') {
            jCount++;
        }
        else if (p == 'O') {
            oCount++;
        }
        else if (p == 'I') {
            iCount++;
        }
        jPref.push_back(jCount);
        oPref.push_back(oCount);
        iPref.push_back(iCount); 
    }

    int counter = 200001;

    for (int p = 1; p < n + 1; p++) {
        int jPos = find(jPref[p - 1] + k, p, jPref);
        // cout << jPos << ' ';
        if (jPos == -1) {
            break;
        }
        int oPos = find(oPref[jPos] + k, jPos, oPref);
        // cout << oPos << ' ';
        if (oPos == -1) {
            break;
        }
        int iPos = find(iPref[oPos] + k, oPos, iPref);
        // cout << iPos << ' ';
        if (iPos == -1) {
            break;
        }
        // cout << counter << endl;
        counter = min(counter, iPos - p - 3 * k + 1);
    }
    cout << counter;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 436 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 436 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 436 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -