oj.uz

Submission #43526

# Submission time Handle Problem Language Result Execution time Memory
43526 2018-03-17T10:33:24 Z ffresh JOIOJI (JOI14_joioji) C++14
95 / 100
 84 ms 9752 KB 
#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=1;i<=3;++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=1;i<=3;++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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 476 KB Output is correct
6 Correct 1 ms 528 KB Output is correct
7 Correct 1 ms 548 KB Output is correct
8 Correct 1 ms 548 KB Output is correct
9 Incorrect 1 ms 548 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

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

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 988 KB Output is correct
2 Correct 11 ms 1884 KB Output is correct
3 Correct 17 ms 2780 KB Output is correct
4 Correct 35 ms 5212 KB Output is correct
5 Correct 76 ms 7420 KB Output is correct
6 Correct 81 ms 9752 KB Output is correct
7 Correct 80 ms 9752 KB Output is correct
8 Correct 84 ms 9752 KB Output is correct
9 Correct 79 ms 9752 KB Output is correct
10 Correct 81 ms 9752 KB Output is correct
11 Correct 53 ms 9752 KB Output is correct
12 Correct 71 ms 9752 KB Output is correct
13 Correct 78 ms 9752 KB Output is correct
14 Correct 46 ms 9752 KB Output is correct
15 Correct 58 ms 9752 KB Output is correct