Submission #5880

#	Time	Username	Problem	Language	Result	Execution time	Memory
5880		kriii	JOIOJI (JOI14_joioji)	C++98	100 / 100	360 ms	4176 KiB

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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80