Submission #202301

#	Time	Username	Problem	Language	Result	Execution time	Memory
202301		amoo_safar	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	15 ms	5884 KiB

ho_t2

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

ll J[N], O[N], I[N];
vector<ll> v;

ll calc(ll x){
	return I[O[J[x]]];
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, k;
	cin >> n >> k;
	str s;
	cin >> s;
	J[n] = n;
	O[n] = n;
	I[n] = n;
	v.clear();
	for(int i = n - 1; i >= 0; i--){
		if(s[i] == 'J') v.pb(i);
		J[i] = (v.size() < k ? n : v[v.size() - k]);
	}
	v.clear();
	for(int i = n - 1; i >= 0; i--){
		if(s[i] == 'O') v.pb(i);
		O[i] = (v.size() < k ? n : v[v.size() - k]);
	}
	v.clear();
	for(int i = n - 1; i >= 0; i--){
		if(s[i] == 'I') v.pb(i);
		I[i] = (v.size() < k ? n : v[v.size() - k]);
	}
	if(calc(0) == n) return cout << "-1\n", 0;
	ll ans = n;
	for(int i = 0; i < n; i++){
		if(calc(i) == n) break;
		ans = min(ans, (calc(i) - i + 1) - 3*k);
	}
	cout << ans;
	return 0;
}
/*
5
4 7 9 10 11 12
3 5 7 9 11
*/

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   J[i] = (v.size() < k ? n : v[v.size() - k]);
           ~~~~~~~~~^~~
ho_t2.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   O[i] = (v.size() < k ? n : v[v.size() - k]);
           ~~~~~~~~~^~~
ho_t2.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   I[i] = (v.size() < k ? n : v[v.size() - k]);
           ~~~~~~~~~^~~

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87