QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#716512 | #9586. 野兽节拍 | qzez# | WA | 17ms | 17916kb | C++14 | 1.6kb | 2024-11-06 15:25:58 | 2024-11-06 15:25:59 |
Judging History
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'