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<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<pll, pll>
#define pdd pair<double, double>
#define pu push_back
#define po pop_back
#define fi first
#define se second
#define fifi fi.fi
#define fise fi.se
#define sefi se.fi
#define sese se.se
#define cekcek cout<<'c'<<'e'<<'k'<<endl
using namespace std;
ll N, K, ans, sum, temp, L, R, mid, pos;
char a;
vector<ll> v[3];
int main(){
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
cin >> N >> K;
for(ll i = 1; i <= N; i++){
cin >> a;
if(a == 'J') v[0].pu(i);
else if(a == 'O') v[1].pu(i);
else v[2].pu(i);
}
sort(v[0].begin(), v[0].end());
sort(v[1].begin(), v[1].end());
sort(v[2].begin(), v[2].end());
//for(auto i : v[2]) cout << i << " ";
ans = 1e15;
for(ll i = K - 1; i < v[2].size(); i++){
//cari I
sum = v[2][i] - v[2][i - (K - 1)] - (K - 1);
// cari O
pos = -1;
L = 0;
R = v[1].size() - 1;
ll cari = v[2][i - (K - 1)];
while(L <= R){
mid = (L + R) / 2;
if(v[1][mid] < cari){
L = mid + 1;
pos = mid;
}
else R = mid - 1;
}
if(pos < K - 1) continue;
sum += cari - v[1][pos] - 1;
sum += v[1][pos] - v[1][pos - (K - 1)] - (K - 1);
// cari J
L = 0;
R = v[0].size() - 1;
cari = v[1][pos - (K - 1)];
pos = -1;
while(L <= R){
mid = (L + R) / 2;
if(v[0][mid] < cari){
L = mid + 1;
pos = mid;
}
else R = mid - 1;
}
if(pos < K - 1) continue;
sum += cari - v[0][pos] - 1;
sum += v[0][pos] - v[0][pos - (K - 1)] - (K - 1);
ans = min(ans, sum);
}
if(ans > 1e9) cout << -1 << endl;
else cout << ans << endl;
}
Compilation message (stderr)
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:62:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(ll i = K - 1; i < v[2].size(); i++){
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |