| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1098561 |
2024-10-09T15:24:12 Z |
Nurislam |
JJOOII 2 (JOI20_ho_t2) |
C++17 |
|
0 ms |
344 KB |
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;z
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
//#define ordst tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag , tree_order_statistics_node_update >
//#define double long double
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const int N = (1<<18) +1, inf = 1e18+200;
//int mod = 998244353;
//int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
void solve(){
map<char,int> mp;
mp['J'] = 0;
mp['O'] = 1;
mp['I'] = 2;
vector<int> a;a.pb(-1);
auto conv = [&](string s)->void{
for(auto &i:s)a.pb(mp[i]);
};
int n, k;
cin >> n >> k;
string s;cin >> s;conv(s);
vector<vector<int>> pref(n+1, vector<int> (3, 0));
for(auto &i:pref[0])i = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j < 3; j++)
pref[i][j] = pref[i-1][j];
pref[i][a[i]]++;
}
auto get = [&](int l, int r, int t) -> int{
return pref[r][t] - pref[l-1][t];
};
auto ch = [&]()->bool{
vector<int> v;
for(int i = 1; i <= n; i++)if(a[i] == 1)v.pb(i);
for(int i = 0; i < (int)v.size(); i++){
if(i+k-1 == (int)v.size())break;
int l = v[i], r = v[i+k-1];
if(get(1, l, 0) >= k && get(r, n, 2) >= k)return true;
}
return false;
};
if(!ch()){cout << "-1\n";return;}
vector<int> v;
for(int i = 1; i <= n; i++)if(a[i] == 1)v.pb(i);
int ans = inf;
int il = 0, ir = k-1;
int last = inf;
while(ir < v.size()){
//cout << il << ' ' << ir << '\n';
int l = v[il]-1, r = v[ir]+1;
int tol = l;
for(int i = 20; i >= 0; i--){
int nwl = max(1ll, tol-(1<<i));
if(get(nwl, l, 0) >= k)continue;
tol = nwl;
}
tol--;
int tor = r;
for(int i = 20; i >= 0; i--){
int nwr = min(n, tor+(1<<i));
if(get(r, nwr, 2) >= k)continue;
tor = nwr;
}
tor++;
int cur = tor-tol+1 - k*3;
chmin(ans, cur);
if(ir-il+1 == k)ir++;
else if(ir+1 == v.size())il++;
else if(chmin(last, cur))ir++;
else il++;
//cout << il << ' ' << ir << '\n';
}
cout << ans << '\n';
}
signed main(){
//ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while(tt--){
solve();
}
}
Compilation message
ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:81:11: 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]
81 | while(ir < v.size()){
| ~~~^~~~~~~~~~
ho_t2.cpp:102:16: 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]
102 | else if(ir+1 == v.size())il++;
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
