Submission #251889

#	Time	Username	Problem	Language	Result	Execution time	Memory
251889		ivandasfs	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	9 ms	3200 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 200004;

char c[200005];

int nxtj[200005];
int nxto[200005];
int nxti[200005];

int main() {
	for (int i=0 ; i<200005 ; i++) {
		nxtj[i] = nxto[i] = nxti[i] = INF;
	}
	int n, k;
	scanf("%d%d", &n, &k);
	string s;
	scanf("%s", c);
	s = c;
	int cntj = 0;
	int cnto = 0;
	int cnti = 0;
	for (int i=0 ; i<n ; i++) {
		if (s[i] == 'J') {
			cntj++;
			if (cntj == k) nxtj[0] = i;
		}
		if (s[i] == 'O') {
			cnto++;
			if (cnto == k) nxto[0] = i;
		}
		if (s[i] == 'I') {
			cnti++;
			if (cnti == k) nxti[0] = i;
		}
	}
	//cout <<nxtj[0]<<nxto[0]<<nxti[0]<<endl;
	if (nxtj[0] == INF or nxto[0] == INF or nxti[0] == INF) {
		printf("-1\n");
		return 0;
	}
	for (int i=1 ; i<n ; i++) {
		nxtj[i] = nxtj[i-1];
		nxto[i] = nxto[i-1];
		nxti[i] = nxti[i-1];
		if (s[i-1] == 'J') {
			if (nxtj[i] < n) nxtj[i]++;
			while (nxtj[i]<n and s[nxtj[i]]!='J') nxtj[i]++;
		}
		if (s[i-1] == 'O') {
			if (nxto[i] < n) nxto[i]++;
			while (nxto[i]<n and s[nxto[i]]!='O') nxto[i]++;
		}
		if (s[i-1] == 'I') {
			if (nxti[i] < n) nxti[i]++;
			while (nxti[i]<n and s[nxti[i]]!='I') nxti[i]++;
		}
	//	cout <<nxtj[i]<<nxto[i]<<nxti[i]<<endl;
	}
	int maxx = -1;
	for (int i=0 ; i<n ; i++) {
		int end = nxti[nxto[nxtj[i]]];
	//	cout <<"end = "<<end<<endl;
		if (end >= n) break;
		maxx = max(maxx, i+n-end-1);
	}
	if (maxx == -1) {
		printf("-1\n");
	} else {
		printf("%d\n", n-3*k-maxx);
	}
	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
ho_t2.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", c);
  ~~~~~^~~~~~~~~

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