| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 120216 | errorgorn | JOIOJI (JOI14_joioji) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <unordered_map>
#include <utility>
#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> ii;
int n;
char c;
string s;
struct custom_hash{
size_t operator()(const pair<int,int> &i)const{
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
}
};
unordered_map<ii,int,custom_hash> suffix;
int arr[3];
int pre[3];
int main(){
suffix.reserve(4096);
suffix.max_load_factor(0.25);
//freopen("input.txt","r",stdin);
scanf("%d",&n);
getchar();
c=getchar();
while (c!='\n'){
s+=c;
if (c=='J') arr[0]++;
else if (c=='O') arr[1]++;
else arr[2]++;
c=getchar();
}
suffix[ii(0,0)]=0;
for (int x=0;x<3;x++) pre[x]=arr[x];
for (int x=0;x<s.size();x++){
if (s[x]=='J') pre[0]--;
else if (s[x]=='O') pre[1]--;
else pre[2]--;
suffix[ii(pre[0]-pre[1],pre[0]-pre[2])]=x+1;
}
memset(pre,0,sizeof(pre));
int ans=0;
int a=arr[0]-arr[1],b=arr[0]-arr[2];
for (int x=0;x<s.size();x++){
ans=max(ans,suffix[ii(a-(pre[0]-pre[1]),b-(pre[0]-pre[2]))]-x);
if (s[x]=='J') pre[0]++;
else if (s[x]=='O') pre[1]++;
else pre[2]++;
}
printf("%d\n",ans);
}
