Submission #201306

#	Time	Username	Problem	Language	Result	Execution time	Memory
201306		Atalasion	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	35 ms	5380 KiB

ho_t2

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;

int n, k, ps[N][3], ss[N][3], ans, delta[3];
string s;

int BS(int La, int id){
	if (ss[La + 1][id] < k) return -1;
	int l = La, r = n;
	while (r - l > 1){
		int md = (l + r) >> 1;
		if (ps[md][id] - ps[La][id] <= k - 1)l = md;
		else r = md;
	}
	return r;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	cin >> s;
	ans = n + 1;
	for (int i = 0; i < s.size(); i++){
		if (s[i] == 'J') s[i] = '0';
		else if(s[i] == 'O') s[i] = '1';
		else s[i] = '2';
		for (int j = 0; j < 3; j++) ps[i + 1][j] = ps[i][j];
		ps[i + 1][s[i] - '0'] ++;
	}
	for (int i = s.size(); i > 0; i--){
		for (int j = 0; j < 3; j++) ss[i][j] = ss[i + 1][j];
		ss[i][s[i - 1] - '0'] ++; 
	}
	//cout << ss[1][0] << ' ' << ss[1][1] << ' ' << ss[1][2] << '\n';
	for (int i = 0; i < 3; i++){
		if (ps[n][i] < k) return cout << -1, 0;
		delta[i] = ps[n][i] - k;
	}
	int last = -1;
	for (int j = 0; j < 3; j++){
		int cnt = 0;
		for (int i = last + 1; i < n ;i++){
			if (s[i] - '0' == j) cnt++;
			if (cnt == k){
				last = i;
				break;
			} 
		}
		if (cnt != k) return cout << -1, 0;
	}
	//cout << delta[0] << ' ' << delta[1] << ' ' << delta[2] << '\n';
	for (int i = 1; i <= n; i++){
		if (s[i - 1] == '0'){
			int last = BS(i - 1, 0);
			if (last == -1) break;
			last = BS(last, 1);
			if (last == -1) break;
			last = BS(last, 2);
			if (last == -1) break;
			//cout << i << ' ' << last << '\n';
			ans = min(ans, last - i + 1 - 3 * k);
		}	
	}
	cout << ans;








	return 0;
}

Compilation message (stderr)

ho_t2.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise ("ofast")
 
ho_t2.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise("unroll-loops")
 
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++){
                  ~~^~~~~~~~~~

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