| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1111026 |
2024-11-11T10:11:25 Z |
vjudge1 |
JJOOII 2 (JOI20_ho_t2) |
C++11 |
|
16 ms |
3152 KB |
// ███╗ ███╗ █████╗ ██████╗ ███████╗ ██████╗ ██╗ ██╗ ███╗ ███╗ █████╗ ██████╗ ██████╗██╗ ██╗███████╗██╗ ██╗ ██╗ ██╗██╗██╗
// ████╗ ████║██╔══██╗██╔══██╗██╔════╝ ██╔══██╗╚██╗ ██╔╝██╗ ████╗ ████║██╔══██╗██╔══██╗██╔════╝██║ ██║██╔════╝██║ ██║ ██║ ██║██║██║
// ██╔████╔██║███████║██║ ██║█████╗ ██████╔╝ ╚████╔╝ ╚═╝ ██╔████╔██║███████║██████╔╝██║ ███████║█████╗ ██║ ██║ ███████║██║██║
// ██║╚██╔╝██║██╔══██║██║ ██║██╔══╝ ██╔══██╗ ╚██╔╝ ██╗ ██║╚██╔╝██║██╔══██║██╔══██╗██║ ██╔══██║██╔══╝ ██║ ██║ ██╔══██║██║██║
// ██║ ╚═╝ ██║██║ ██║██████╔╝███████╗ ██████╔╝ ██║ ╚═╝ ██║ ╚═╝ ██║██║ ██║██║ ██║╚██████╗██║ ██║███████╗███████╗███████╗█████╗██║ ██║██║██║
// ╚═╝ ╚═╝╚═╝ ╚═╝╚═════╝ ╚══════╝ ╚═════╝ ╚═╝ ╚═╝ ╚═╝╚═╝ ╚═╝╚═╝ ╚═╝ ╚═════╝╚═╝ ╚═╝╚══════╝╚══════╝╚══════╝╚════╝╚═╝ ╚═╝╚═╝╚═╝
// ඞ
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣤⣤⣤⣤⣤⣤⣤⣤⣄⡀
// ⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⡿⠛⠉⠉⠉⠉⠉⠉⠻⢿⣿⣷⡄
// ⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⠋⠀⠀⠀⠀⠀⠀⠀ ⢻⣿⣿⡄
// ⠀⠀⠀⠀⠀⠀⠀⣸⣿⡏⠀⠀⠀ ⣠⣾⣿⣿⣿⠿⠿⠿⢿⣿⣿⣄
// ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠁⠀⠀ ⣿⣿⣯⠁⠀⠀⠀⠀⠀ ⠙⢿⣷⡄
// ⠀⠀⣀⣤⣴⣶⣶⣿⡟⠀⠀⠀ ⣿⣿⣿ ⣿⣷
// ⠀⢰⣿⡟⠋⠉⣹⣿⡇⠀⠀⠀ ⣿⣿⣿⣷⣦⣀⣀⣀⣀⣀⣀⣀⣿⣿
// ⢸⣿⡇ ⣿⣿⡇⠀⠀ ⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
// ⣸⣿⡇ ⣿⣿⡇⠀⠀⠀⠀ ⠉⠉⠉⠉⠉⠉⠉⠉⠉⡿⢻⡇
// ⠀⣿⣿ ⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢸⣿⡇
// ⠀⣿⣿⠀ ⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢸⣿⡇
// ⠀⣿⣿⠀⠀ ⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢸⣿⡇
// ⠀⢿⣿ ⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⣿⡇
// ⠀⠸⣿⣦⡀⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⣿⣿
// ⠀⠀⠛⢿⣿⣿⣿⣿⡇ ⠀⣠⣿⣿⣿⣿⣄ ⣿⣿
// ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠀⠀⠀⠀⠀⣿⣿⡇⠀⣽⣿⡆ ⢸⣿⡇
// ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠀⠀⠀⠀⠀⣿⣿⡇⠀⢹⣿⡆⠀⠀ ⣸⣿⠇
// ⠀⠀⠀⠀⠀⠀⠀⢿⣿⣦⣄⣀⣠⣴⣿⣿ ⠀⠈⠻⣿⣿⣿⣿⡿⠏
// ⠀⠀⠀⠀⠀⠀⠀⠈⠛⠻⠿⠿⠿⠿⠋⠁
#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
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 |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Correct |
1 ms |
336 KB |
Output is correct |
| 18 |
Correct |
1 ms |
336 KB |
Output is correct |
| 19 |
Correct |
1 ms |
336 KB |
Output is correct |
| 20 |
Correct |
1 ms |
528 KB |
Output is correct |
| 21 |
Correct |
1 ms |
336 KB |
Output is correct |
| 22 |
Correct |
1 ms |
336 KB |
Output is correct |
| 23 |
Correct |
1 ms |
336 KB |
Output is correct |
| 24 |
Correct |
1 ms |
336 KB |
Output is correct |
| 25 |
Correct |
1 ms |
336 KB |
Output is correct |
| 26 |
Correct |
1 ms |
504 KB |
Output is correct |
| 27 |
Correct |
1 ms |
336 KB |
Output is correct |
| 28 |
Correct |
1 ms |
336 KB |
Output is correct |
| 29 |
Correct |
1 ms |
336 KB |
Output is correct |
| 30 |
Correct |
1 ms |
336 KB |
Output is correct |
| 31 |
Correct |
1 ms |
336 KB |
Output is correct |
| 32 |
Correct |
1 ms |
336 KB |
Output is correct |
| 33 |
Correct |
1 ms |
460 KB |
Output is correct |
| 34 |
Correct |
1 ms |
336 KB |
Output is correct |
| 35 |
Correct |
1 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Correct |
1 ms |
336 KB |
Output is correct |
| 18 |
Correct |
1 ms |
336 KB |
Output is correct |
| 19 |
Correct |
1 ms |
336 KB |
Output is correct |
| 20 |
Correct |
1 ms |
528 KB |
Output is correct |
| 21 |
Correct |
1 ms |
336 KB |
Output is correct |
| 22 |
Correct |
1 ms |
336 KB |
Output is correct |
| 23 |
Correct |
1 ms |
336 KB |
Output is correct |
| 24 |
Correct |
1 ms |
336 KB |
Output is correct |
| 25 |
Correct |
1 ms |
336 KB |
Output is correct |
| 26 |
Correct |
1 ms |
504 KB |
Output is correct |
| 27 |
Correct |
1 ms |
336 KB |
Output is correct |
| 28 |
Correct |
1 ms |
336 KB |
Output is correct |
| 29 |
Correct |
1 ms |
336 KB |
Output is correct |
| 30 |
Correct |
1 ms |
336 KB |
Output is correct |
| 31 |
Correct |
1 ms |
336 KB |
Output is correct |
| 32 |
Correct |
1 ms |
336 KB |
Output is correct |
| 33 |
Correct |
1 ms |
460 KB |
Output is correct |
| 34 |
Correct |
1 ms |
336 KB |
Output is correct |
| 35 |
Correct |
1 ms |
504 KB |
Output is correct |
| 36 |
Correct |
15 ms |
2240 KB |
Output is correct |
| 37 |
Correct |
15 ms |
2624 KB |
Output is correct |
| 38 |
Correct |
16 ms |
2892 KB |
Output is correct |
| 39 |
Correct |
15 ms |
2708 KB |
Output is correct |
| 40 |
Correct |
14 ms |
2916 KB |
Output is correct |
| 41 |
Correct |
14 ms |
2884 KB |
Output is correct |
| 42 |
Correct |
16 ms |
2624 KB |
Output is correct |
| 43 |
Correct |
8 ms |
1992 KB |
Output is correct |
| 44 |
Correct |
10 ms |
1904 KB |
Output is correct |
| 45 |
Correct |
13 ms |
3072 KB |
Output is correct |
| 46 |
Correct |
13 ms |
2832 KB |
Output is correct |
| 47 |
Correct |
12 ms |
2756 KB |
Output is correct |
| 48 |
Correct |
13 ms |
2756 KB |
Output is correct |
| 49 |
Correct |
8 ms |
1744 KB |
Output is correct |
| 50 |
Correct |
12 ms |
2756 KB |
Output is correct |
| 51 |
Correct |
13 ms |
2752 KB |
Output is correct |
| 52 |
Correct |
9 ms |
2244 KB |
Output is correct |
| 53 |
Correct |
10 ms |
3012 KB |
Output is correct |
| 54 |
Correct |
11 ms |
3152 KB |
Output is correct |
| 55 |
Correct |
10 ms |
3152 KB |
Output is correct |
| 56 |
Correct |
8 ms |
3112 KB |
Output is correct |
