#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, b) for(int i = 0; i < (int)b; i++)
#define FOR(i, a, b) for(int i = a; i < (int)b; i++)
#define dbg(v) cerr << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
#define debug(a, b) cerr << "[" << #a << ", " << #b << "] = [" << a << ", " << b << "]\n";
template<class T> inline void read(T& t){ cin >> t; }
template<class T, class... H> inline void read(T& t, H&... h){ cin >> t; read(h...); }
template<class T> inline void read(vector<T>& t){ for(auto&x : t) read(x); }
template<class T, class... H> inline void read(vector<T>& t, vector<H>&... h){ read(t); read(h...); }
template<class T> inline void wt(const T t) { cout << t; }
template<class T> inline void write(const T t) { cout << t << " "; }
template<class T> inline void print(const T t){ cout << t << "\n";}
template<class T, class... H> inline void wt(const T& t, const H&... h){ cout << t; wt(h...); }
template<class T, class... H> inline void print(const T& t, const H&... h){ cout << t; cout << " "; print(h...);}
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(a) (int)a.size()
bool bs(vector<int>&a, int x){
return binary_search(all(a), x);
}
int a, b, c;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, k; string s; read(n, k, s);
vector<int> pre_j(n + 1, 0), pre_o(n + 1, 0), pre_i(n + 1, 0);
// build prefix sum
rep(i, n){
pre_j[i + 1] = pre_j[i] + (s[i] == 'J');
pre_o[i + 1] = pre_o[i] + (s[i] == 'O');
pre_i[i + 1] = pre_i[i] + (s[i] == 'I');
}
int Min = 1e9, pos_j = 0, l = 0, cnt = 0;
while(s[l] != 'J') l++;
l++;
while(true){
if(bs(pre_j, pre_j[pos_j] + k)){
a = lower_bound(all(pre_j), pre_j[pos_j] + k) - pre_j.begin(); pos_j = a;
}else break;
if(bs(pre_o, pre_o[a] + k)){
b = lower_bound(all(pre_o), pre_o[a] + k) - pre_o.begin();
}else break;
if(bs(pre_i, pre_i[b] + k)){
c = lower_bound(all(pre_i), pre_i[b] + k) - pre_i.begin();
}else break;
// print(a, b, c);
Min = min(Min, c - (!cnt ? l : a) + 1 - 3 * k); cnt++;
}
print(Min == (int)1e9 ? -1 : Min);
return 0;
}
/*
JOI 2020 JJOOII
- For each starting point...
- Find the next point such that the number of "J"s between it and the starting
point is equal to K
- Find the next point such that the number of "O"s between it and the previous
point is equal to K
- Find the next point such that the number of "I"s between it and the previous
point is equal to K
- Notice how this is always optimal because we want to minimize the distance
between the first and last points
- We can use 4 pointers and prefix sums to find the 4 points for each starting point
- Complexity: O(N)
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
