| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 753799 |
2023-06-06T05:29:49 Z |
vjudge1 |
JJOOII 2 (JOI20_ho_t2) |
C++17 |
|
1 ms |
340 KB |
// Bolatulu
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define int long
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define F first
#define S second
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
using namespace std;
const ll INF = LONG_MAX;
const int N = 2e6;
const int M = 1e9 + 7;
const ll HZ = 998244353;
const int MAX = INT_MAX;
const int MIN = INT_MIN;
const db pi = 3.141592653;
const int P=31;
int n,k,ps[3][N];
string s;
int find_pos(int L,int R,int val) {
int l=L,r=R;
while (l+1<r) {
int mid=(l+r)/2;
if (ps[val][mid]-ps[val][L]<k)
l=mid;
else
r=mid;
}
return r;
}
void solve() {
s += ' ';
string t;
cin >> n >> k >> t;
s += t;
for (int i = 1; i < s.size(); i++) {
for (int j = 0; j < 3; j++)
ps[j][i] = ps[j][i - 1];
if (s[i] == 'J')
ps[0][i]++;
if (s[i] == 'O')
ps[1][i]++;
if (s[i] == 'I')
ps[2][i]++;
}
int l = 0, r = 1, mn = INT_MAX;
while (r < s.size()) {
int z1 = find_pos(l, r, 0), z2 = find_pos(z1, r, 1), z3 = find_pos(z2, r, 0);
while (r < s.size() and (ps[0][z1] - ps[0][l] < k or ps[1][z2] - ps[1][z1] < k or ps[2][z3] - ps[2][z2] < k)) {
r++;
z1 = find_pos(l, r, 0), z2 = find_pos(z1, r, 1), z3 = find_pos(z2, r, 0);
}
if (r==s.size() and l==0) {
cout << -1;
return;
}
z1 = find_pos(l, r, 0), z2 = find_pos(z1, r, 1), z3 = find_pos(z2, r, 0);
while (l < r and (ps[0][z1] - ps[0][l] >= k and ps[1][z2] - ps[1][z1] >= k and ps[2][z3] - ps[2][z2] >= k)) {
mn = min(mn, r - l);
l++;
z1 = find_pos(l, r, 0), z2 = find_pos(z1, r, 1), z3 = find_pos(z2, r, 0);
}
}
cout << mn - k * 3;
}
signed main() {
// freopen("262144.in", "r", stdin);
// freopen("262144.out", "w", stdout);
kanagattandirilmagandiktarinizdan
int test = 1;
// cin >> test;
for (int i=1;i<=test;i++) {
// cout << "Case " << i << ':' << '\n';
solve();
// cout << '\n';
}
return 0;
}
Compilation message
ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:47:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 1; i < s.size(); i++) {
| ~~^~~~~~~~~~
ho_t2.cpp:58:14: warning: comparison of integer expressions of different signedness: 'long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | while (r < s.size()) {
| ~~^~~~~~~~~~
ho_t2.cpp:60:18: warning: comparison of integer expressions of different signedness: 'long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | while (r < s.size() and (ps[0][z1] - ps[0][l] < k or ps[1][z2] - ps[1][z1] < k or ps[2][z3] - ps[2][z2] < k)) {
| ~~^~~~~~~~~~
ho_t2.cpp:64:14: warning: comparison of integer expressions of different signedness: 'long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | if (r==s.size() and l==0) {
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
