QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#766614 | #9586. 野兽节拍 | forget-star# | TL | 2ms | 11824kb | C++20 | 2.1kb | 2024-11-20 17:57:56 | 2024-11-20 17:57:57 |
Judging History
answer
#include<bits/stdc++.h>
//#define int long long
#define fr(i,a,b) for(int i(a),end##i(b);i<=end##i;i++)
#define fd(i,a,b) for(int i(a),end##i(b);i>=end##i;i--)
#define de fprintf(stderr,"on-%d\n",__LINE__)
using namespace std;
const int maxn=4e6+5;
int n;
char c[maxn];
int nex[maxn],pre[maxn];
int to[maxn];
int cnt=0;
#define pii pair<int*,int>
#define fi first
#define se second
#define mk make_pair
pii st[maxn];
int top;
void insert(int* a){
st[++top]=mk(a,*a);
}
int solve(int x,int y,int z,int p){
//cnt++;
//cerr<<p<<'\n';
int ans=0;
top=0;
while(1){
if(c[p]==0||c[nex[p]]==0||c[nex[nex[p]]]==0)break;
if(c[p]==x&&c[nex[p]]==y&&c[nex[nex[p]]]==z){
ans++;
insert(&nex[pre[p]]);
insert(&pre[nex[pre[p]]]);
nex[pre[p]]=nex[nex[nex[p]]];
pre[nex[pre[p]]]=pre[p];
int go=to[p];
if(go==nex[p])go=to[go];
if(go==nex[nex[p]])go=to[go];
if(c[pre[pre[p]]]==x&&c[pre[p]]==y){
if(y!=x){
insert(&to[pre[pre[p]]]);
to[pre[pre[p]]]=go;
p=pre[pre[p]];
}
else {
insert(&to[pre[p]]);
to[pre[p]]=go;
p=pre[pre[p]];
}
}
else if(c[pre[p]]==x){
insert(&to[pre[p]]);
to[pre[p]]=go;
p=pre[p];
}
else {
p=go;
}
}
else {
p=to[p];
}
}
while(top){
*st[top].fi=st[top].se;
top--;
}
return ans;
}
int F[100];
vector<int> ANS;
bool operator <(vector<int> A,vector<int> B){
fr(i,0,2)if(A[i]<B[i])return 1;
return 0;
}
signed main(){
#ifdef pig
freopen("pig.in","r",stdin);
freopen("pig.out","w",stdout);
#endif
cin>>n;
scanf("%s",c+1);
fr(i,1,n)c[i]=c[i]-'a'+1;
fr(i,1,n-1){
nex[i]=i+1;
pre[i+1]=i;
}
fd(i,n,1){
to[i]=F[c[i]];
F[c[i]]=i;
}
int ans=0;
ANS.resize(3);
ANS[0]=c[1];
ANS[1]=c[2];
ANS[2]=c[3];
fr(i,1,26)if(F[i])fr(j,1,26)if(F[j])fr(k,1,26)if(F[k]){
// cerr<<i<<' '<<j<<' '<<k<<'\n';
int t=solve(i,j,k,F[i]);
vector<int> now;
now.resize(3);now[0]=i;now[1]=j;now[2]=k;
if(t>ans||t==ans&&now<ANS){
ans=t;
ANS=now;
}
}
//cout<<cnt<<'\n';
cout<<ans<<'\n';
fr(i,0,2)putchar(ANS[i]+'a'-1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11824kb
input:
10 aaababbaab
output:
3 aab
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 11812kb
input:
14 liaoningdalian
output:
2 lia
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 11764kb
input:
3 zyl
output:
1 zyl
result:
ok 2 lines
Test #4:
score: -100
Time Limit Exceeded
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababababababababaaaaaaaaaaaaaaaaaacacacacacacacacacacacacacacacacacaaaaaaaaaaaaaaaaaadadadadadadadadadadadadadadadadadaaaaaaaaaaaaaaaaaaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaaaaaaaaaaaaaaaaaafafafafafafafafafafa...