QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#716512#9586. 野兽节拍qzez#WA 17ms17916kbC++141.6kb2024-11-06 15:25:582024-11-06 15:25:59

Judging History

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

  • [2024-11-06 15:25:59]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:17916kb
  • [2024-11-06 15:25:58]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
#define LB lower_bound
using namespace std;using ll=long long;using pii=pair<int,int>;
const int N=1e6+5;
int n;char s[N];
vector<int> S[26][26][26];
int pre[N],nxt[N];
int st[N],sh;
void del(int x){
	st[++sh]=x;
	pre[nxt[x]]=pre[x];
	nxt[pre[x]]=nxt[x];
}
void ins(int x){
	pre[nxt[x]]=nxt[pre[x]]=x;
}
int calc(int a,int b,int c){
	int p=1,pt=0;
	int cnt=0;
	while(p<=n){
		if(pre[pre[p]]>0&&s[pre[pre[p]]]==a&&s[pre[p]]==b&&s[p]==c){
			p=nxt[p];
			del(pre[pre[pre[p]]]);
			del(pre[pre[p]]);
			del(pre[p]);
			cnt++;
			continue;
		} 
		if(pre[p]>0&&nxt[p]<=n&&s[pre[p]]==a&&s[p]==b&&s[nxt[p]]==c){
			p=nxt[nxt[p]];
			del(pre[pre[p]]);
			del(pre[p]);
			del(p);
			cnt++;
			continue;
		}
		if(nxt[p]<=n&&nxt[nxt[p]]<=n&&s[p]==a&&s[nxt[p]]==b&&s[nxt[nxt[p]]]==c){
			p=nxt[nxt[nxt[p]]];
			del(pre[pre[p]]);
			del(pre[p]);
			del(p);
			cnt++;
			continue;
		}
		while(pt<S[a][b][c].size()&&S[a][b][c][pt]<p) pt++;
		if(pt==S[a][b][c].size()) break;
		p=S[a][b][c][pt]+3;
		del(p-3);del(p-2);del(p-1);
		cnt++;
	}
	while(sh) ins(st[sh]),sh--;
	return cnt;
}
void Solve(){
	scanf("%d%s",&n,s+1);
	for(int i=0;i<=n;i++) nxt[i]=i+1,pre[i+1]=i;
	for(int i=1;i<=n;i++) s[i]-='a';
	for(int i=2;i<n;i++) S[s[i-1]][s[i]][s[i+1]].push_back(i-1);
	int tot=0,a1,a2,a3;
	for(int x=0;x<26;x++) for(int y=0;y<26;y++) for(int z=0;z<26;z++){
		int w=calc(x,y,z);
		if(w>tot) tot=w,a1=x,a2=y,a3=z;
	}
	printf("%d\n%c%c%c",tot,a1+'a',a2+'a',a3+'a');
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 10156kb

input:

10
aaababbaab

output:

3
aab

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 8496kb

input:

14
liaoningdalian

output:

2
lia

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 10056kb

input:

3
zyl

output:

1
zyl

result:

ok 2 lines

Test #4:

score: -100
Wrong Answer
time: 17ms
memory: 17916kb

input:

896376
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababababababababaaaaaaaaaaaaaaaaaacacacacacacacacacacacacacacacacacaaaaaaaaaaaaaaaaaadadadadadadadadadadadadadadadadadaaaaaaaaaaaaaaaaaaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaaaaaaaaaaaaaaaaaafafafafafafafafafafa...

output:

4342
aaa

result:

wrong answer 1st lines differ - expected: '3717', found: '4342'