oj.uz

Submission #1098559

# Submission time Handle Problem Language Result Execution time Memory
1098559 2024-10-09T15:16:02 Z Nurislam JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 1 ms 348 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 < v.size(); i++){
			if(i+k-1 == 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;
	for(int i = 0; i < v.size(); i++){
		if(i+k-1 == v.size())break;
		
		int l = v[i], r = v[i+k-1];
		int tol = l;
		for(int i = 18; 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 = 18; i >= 0; i--){
			int nwr = min(n, tor+(1<<i));
			if(get(r, nwr, 2) >= k)continue;
			tor = nwr;
		}
		tor++;
		
		chmin(ans, tor-tol+1 - k*3);
	}
	
	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 lambda function:
ho_t2.cpp:66:20: 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]
   66 |   for(int i = 0; i < v.size(); i++){
      |                  ~~^~~~~~~~~~
ho_t2.cpp:67:13: 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]
   67 |    if(i+k-1 == v.size())break;
      |       ~~~~~~^~~~~~~~~~~
ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:79:19: 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]
   79 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
ho_t2.cpp:80:12: 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]
   80 |   if(i+k-1 == v.size())break;
      |      ~~~~~~^~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -