| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1101825 | BlueGlaucus1 | JJOOII 2 (JOI20_ho_t2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int n;
int binarysearch(int target, int low, vector<int> &arr) {
int high = n;
int val = -1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] >= val) {
val = mid;
high = mid - 1;
}
else if (arr[mid] < target) {
low = mid + 1;
}
}
return val;
}
int main() {
string s;
int k;
cin >> n;
cin >> k;
cin >> s;
vector<int> prefixj = {0};
vector<int> prefixo = {0};
vector<int> prefixi = {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++;
}
prefixj.push_back(jCount);
prefixo.push_back(oCount);
prefixi.push_back(iCount);
}
int answer = 200001;
for (int i = 1; i <=n; i++) {
int position_of_j = find(prefixj[i - 1] + k, i, prefixj);
if (position_of_j == -1) {
break;
}
int position_of_o = find(prefixo[position_of_j] + k, position_of_j, prefixo);
if (position_of_o == -1) {
break;
}
int position_of_i = find(prefixi[position_of_o] + k, position_of_o, prefixi);
if (position_of_i == -1) {
break;
}
answer = min(answer, position_of_i - i - 3 * k + 1);
}
if (answer == 200001) {
answer = -1;
}
cout << answer;
}