| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 43527 |
2018-03-17T10:36:11 Z |
ffresh |
JOIOJI (JOI14_joioji) |
C++14 |
|
111 ms |
9804 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=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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
480 KB |
Output is correct |
| 3 |
Correct |
2 ms |
556 KB |
Output is correct |
| 4 |
Correct |
2 ms |
556 KB |
Output is correct |
| 5 |
Correct |
2 ms |
556 KB |
Output is correct |
| 6 |
Correct |
2 ms |
556 KB |
Output is correct |
| 7 |
Correct |
2 ms |
576 KB |
Output is correct |
| 8 |
Correct |
1 ms |
580 KB |
Output is correct |
| 9 |
Correct |
2 ms |
580 KB |
Output is correct |
| 10 |
Correct |
2 ms |
600 KB |
Output is correct |
| 11 |
Correct |
2 ms |
644 KB |
Output is correct |
| 12 |
Correct |
2 ms |
672 KB |
Output is correct |
| 13 |
Correct |
2 ms |
676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
680 KB |
Output is correct |
| 2 |
Correct |
2 ms |
680 KB |
Output is correct |
| 3 |
Correct |
2 ms |
808 KB |
Output is correct |
| 4 |
Correct |
3 ms |
808 KB |
Output is correct |
| 5 |
Correct |
3 ms |
808 KB |
Output is correct |
| 6 |
Correct |
2 ms |
808 KB |
Output is correct |
| 7 |
Correct |
2 ms |
812 KB |
Output is correct |
| 8 |
Correct |
2 ms |
832 KB |
Output is correct |
| 9 |
Correct |
2 ms |
832 KB |
Output is correct |
| 10 |
Correct |
2 ms |
832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1084 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1980 KB |
Output is correct |
| 3 |
Correct |
21 ms |
2876 KB |
Output is correct |
| 4 |
Correct |
35 ms |
5180 KB |
Output is correct |
| 5 |
Correct |
59 ms |
7500 KB |
Output is correct |
| 6 |
Correct |
81 ms |
9780 KB |
Output is correct |
| 7 |
Correct |
100 ms |
9780 KB |
Output is correct |
| 8 |
Correct |
111 ms |
9780 KB |
Output is correct |
| 9 |
Correct |
81 ms |
9804 KB |
Output is correct |
| 10 |
Correct |
85 ms |
9804 KB |
Output is correct |
| 11 |
Correct |
45 ms |
9804 KB |
Output is correct |
| 12 |
Correct |
54 ms |
9804 KB |
Output is correct |
| 13 |
Correct |
58 ms |
9804 KB |
Output is correct |
| 14 |
Correct |
44 ms |
9804 KB |
Output is correct |
| 15 |
Correct |
57 ms |
9804 KB |
Output is correct |
