QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#766614#9586. 野兽节拍forget-star#TL 2ms11824kbC++202.1kb2024-11-20 17:57:562024-11-20 17:57:57

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 17:57:57]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:11824kb
  • [2024-11-20 17:57:56]
  • 提交

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...

output:


result: