oj.uz

Submission #251888

# Submission time Handle Problem Language Result Execution time Memory
251888 2020-07-22T20:52:08 Z ivandasfs JJOOII 2 (JOI20_ho_t2) C++14
0 / 100
 3 ms 2688 KB 
#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] != INF) nxtj[i]++;
			while (nxtj[i]<n and s[nxtj[i]]!='J') nxtj[i]++;
		}
		if (s[i-1] == 'O') {
			if (nxto[i] != INF) nxto[i]++;
			while (nxto[i]<n and s[nxto[i]]!='O') nxto[i]++;
		}
		if (s[i-1] == 'I') {
			if (nxti[i] != INF) 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 == INF or 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

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
0 / 1.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 87.0

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