Submission #5880

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
5880	2014-05-20T21:38:04 Z	kriii	JOIOJI (JOI14_joioji)	C++	100 / 100	360 ms	4176 KB

joioji

#include <stdio.h>
#include <map>
using namespace std;

struct str
{
	str(int j_, int o_, int i_){
		j = j_; o = o_; i = i_;
	}
	int j,o,i;

	bool operator <(const str& a) const{
		if (j != a.j) return j < a.j;
		if (o != a.o) return o < a.o;
		if (i != a.i) return i < a.i;
		return false;
	}
};

int N,L; char S[200020];

void go(int l, int r)
{
	if (r - l < 2) return;

	int m = (l + r) / 2;
	go(l,m); go(m+1,r);

	int j=0,o=0,i=0;
	map<str, int> chk;
	for (int k=m;k>=l;k--){
		if (S[k] == 'J') j++;
		if (S[k] == 'O') o++;
		if (S[k] == 'I') i++;
		if (j && o && i) j--, o--, i--;
		chk[str(j,o,i)] = k;
	}

	j = o = i = 0;
	for (int k=m+1;k<=r;k++){
		if (S[k] == 'J') j++;
		if (S[k] == 'O') o++;
		if (S[k] == 'I') i++;
		if (j && o && i) j--, o--, i--;
		int m = j;
		if (m < o) m = o;
		if (m < i) m = i;
		str f(m-j,m-o,m-i);
		if (chk.count(f)){
			int l = k - chk[f] + 1;
			if (L < l) L = l;
		}
	}
}

int main()
{
	scanf ("%d %s",&N,S);
	go(0,N-1);
	printf ("%d\n",L);

	return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1404 KB	Output is correct
2	Correct	0 ms	1404 KB	Output is correct
3	Correct	0 ms	1404 KB	Output is correct
4	Correct	0 ms	1404 KB	Output is correct
5	Correct	0 ms	1404 KB	Output is correct
6	Correct	0 ms	1404 KB	Output is correct
7	Correct	0 ms	1404 KB	Output is correct
8	Correct	0 ms	1404 KB	Output is correct
9	Correct	0 ms	1404 KB	Output is correct
10	Correct	0 ms	1404 KB	Output is correct
11	Correct	0 ms	1404 KB	Output is correct
12	Correct	0 ms	1404 KB	Output is correct
13	Correct	0 ms	1404 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1404 KB	Output is correct
2	Correct	0 ms	1404 KB	Output is correct
3	Correct	4 ms	1404 KB	Output is correct
4	Correct	4 ms	1404 KB	Output is correct
5	Correct	0 ms	1404 KB	Output is correct
6	Correct	0 ms	1404 KB	Output is correct
7	Correct	0 ms	1404 KB	Output is correct
8	Correct	0 ms	1404 KB	Output is correct
9	Correct	0 ms	1404 KB	Output is correct
10	Correct	0 ms	1404 KB	Output is correct

Subtask #3

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1404 KB	Output is correct
2	Correct	40 ms	1668 KB	Output is correct
3	Correct	72 ms	1932 KB	Output is correct
4	Correct	156 ms	2328 KB	Output is correct
5	Correct	252 ms	2856 KB	Output is correct
6	Correct	356 ms	2988 KB	Output is correct
7	Correct	348 ms	3120 KB	Output is correct
8	Correct	356 ms	2856 KB	Output is correct
9	Correct	352 ms	3120 KB	Output is correct
10	Correct	360 ms	2724 KB	Output is correct
11	Correct	232 ms	3648 KB	Output is correct
12	Correct	188 ms	2196 KB	Output is correct
13	Correct	192 ms	1800 KB	Output is correct
14	Correct	208 ms	4176 KB	Output is correct
15	Correct	164 ms	1668 KB	Output is correct