oj.uz

Submission #251889

# Submission time Handle Problem Language Result Execution time Memory
251889 2020-07-22T21:00:19 Z ivandasfs JJOOII 2 (JOI20_ho_t2) C++14
100 / 100
 9 ms 3200 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] < 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

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.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 1 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 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct

Subtask #2
12.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 1 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 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 2 ms 2688 KB Output is correct
22 Correct 2 ms 2688 KB Output is correct
23 Correct 2 ms 2688 KB Output is correct
24 Correct 2 ms 2688 KB Output is correct
25 Correct 2 ms 2688 KB Output is correct
26 Correct 2 ms 2688 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2688 KB Output is correct
29 Correct 2 ms 2688 KB Output is correct
30 Correct 2 ms 2688 KB Output is correct
31 Correct 2 ms 2688 KB Output is correct
32 Correct 2 ms 2688 KB Output is correct
33 Correct 2 ms 2688 KB Output is correct
34 Correct 2 ms 2688 KB Output is correct
35 Correct 2 ms 2688 KB Output is correct

Subtask #3
87.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 1 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 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 2 ms 2688 KB Output is correct
22 Correct 2 ms 2688 KB Output is correct
23 Correct 2 ms 2688 KB Output is correct
24 Correct 2 ms 2688 KB Output is correct
25 Correct 2 ms 2688 KB Output is correct
26 Correct 2 ms 2688 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 2 ms 2688 KB Output is correct
29 Correct 2 ms 2688 KB Output is correct
30 Correct 2 ms 2688 KB Output is correct
31 Correct 2 ms 2688 KB Output is correct
32 Correct 2 ms 2688 KB Output is correct
33 Correct 2 ms 2688 KB Output is correct
34 Correct 2 ms 2688 KB Output is correct
35 Correct 2 ms 2688 KB Output is correct
36 Correct 8 ms 3200 KB Output is correct
37 Correct 8 ms 3200 KB Output is correct
38 Correct 8 ms 3200 KB Output is correct
39 Correct 9 ms 3200 KB Output is correct
40 Correct 8 ms 3200 KB Output is correct
41 Correct 9 ms 3200 KB Output is correct
42 Correct 9 ms 3200 KB Output is correct
43 Correct 5 ms 3072 KB Output is correct
44 Correct 7 ms 3072 KB Output is correct
45 Correct 9 ms 3200 KB Output is correct
46 Correct 8 ms 3200 KB Output is correct
47 Correct 8 ms 3200 KB Output is correct
48 Correct 8 ms 3200 KB Output is correct
49 Correct 6 ms 3072 KB Output is correct
50 Correct 9 ms 3200 KB Output is correct
51 Correct 8 ms 3200 KB Output is correct
52 Correct 6 ms 3200 KB Output is correct
53 Correct 6 ms 3200 KB Output is correct
54 Correct 4 ms 3200 KB Output is correct
55 Correct 4 ms 3200 KB Output is correct
56 Correct 4 ms 3200 KB Output is correct