oj.uz

답안 #43525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43525 2018-03-17T10:31:33 Z ffresh JOIOJI (JOI14_joioji) C++14
95 / 100
 108 ms 9724 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){
				ret= max(ret, maxi-temp.second);
			}		
		}
	}
	cout<<ret<<endl;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 496 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Incorrect 2 ms 640 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 692 KB Output is correct
2 Correct 2 ms 692 KB Output is correct
3 Correct 2 ms 700 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 720 KB Output is correct
6 Correct 3 ms 780 KB Output is correct
7 Correct 3 ms 780 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 3 ms 780 KB Output is correct
10 Correct 3 ms 780 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1008 KB Output is correct
2 Correct 15 ms 1984 KB Output is correct
3 Correct 21 ms 2896 KB Output is correct
4 Correct 37 ms 5156 KB Output is correct
5 Correct 63 ms 7420 KB Output is correct
6 Correct 108 ms 9596 KB Output is correct
7 Correct 82 ms 9628 KB Output is correct
8 Correct 80 ms 9628 KB Output is correct
9 Correct 86 ms 9628 KB Output is correct
10 Correct 90 ms 9724 KB Output is correct
11 Correct 48 ms 9724 KB Output is correct
12 Correct 53 ms 9724 KB Output is correct
13 Correct 60 ms 9724 KB Output is correct
14 Correct 51 ms 9724 KB Output is correct
15 Correct 64 ms 9724 KB Output is correct