Submission #43527

#	Time	Username	Problem	Language	Result	Execution time	Memory
43527		ffresh	JOIOJI (JOI14_joioji)	C++14	100 / 100	111 ms	9804 KiB

joioji

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+15,M = 3;


int convert(char x){

	if(x=='I')return 0;
	else if(x=='O')return 1;
	return 2;
}

int sum[N][M];

int Hash[N][M];
#define mp make_pair

bool check(pair<int,pair<int,int> > t){

	if(t.first== t.second.first && t.first== t.second.second)return 1;
	return 0;
}
int main(){
	//freopen("input.txt","r",stdin);


	int n;
	string s;
	cin>>n;
	cin>>s;
	if(n<=2){
		cout<<0<<endl;return 0;
	}
	for(int i=1;i<=(int)s.size();++i){

		for (int j = 0; j < M; ++j){
			sum[i][j]= sum[i-1][j];
		}
		int x =convert(s[i-1]);

		++sum[i][x];
	}


	for(int k=0;k<M;++k){
		for(int i=0;i<=2;++i){
			int pos=1;
			for(int j=i;j<=n;j+=3,++pos){
				Hash[j][k]= sum[j][k]-pos;
			}
		}
	}

	/*cout<<sum[1][2]<<" "<<sum[7][2]<<endl;
	cout<<Hash[1][2]<<" "<<Hash[7][2]<<endl;
	cout<<Hash[1][1]<<" "<<Hash[7][1]<<endl;
	cout<<Hash[1][0]<<" "<<Hash[7][0]<<endl;*/

	int ret=0;
	for(int i=0;i<=2;++i){

		set<pair<pair<int,pair<int,int> >,int> >s;

		for(int j=i;j<=n;j+=3){
			s.insert(  mp( mp(Hash[j][0],mp(Hash[j][1],Hash[j][2]) ),j));
		}
		for(set<pair<pair<int,pair<int,int> >,int> >::iterator it = s.begin();it!= s.end();){
			auto temp = *it;
			auto z = temp.first;
			set<pair<pair<int,pair<int,int> >,int> >::iterator jt;
			int maxi = temp.second;

			for(jt= it;jt!= s.end();++jt){
				auto T = *jt;
				if(T.first!= z)break;
				maxi = T.second;
			}
			it = jt;
			
			if( sum[maxi][0]-sum[temp.second][0]== (maxi-temp.second)/3 || sum[maxi][1]-sum[temp.second][1]== (maxi-temp.second)/3 || sum[maxi][2]-sum[temp.second][2]== (maxi-temp.second)/3){
				ret= max(ret, maxi-temp.second);
			}		
		}
	}
	cout<<ret<<endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80