QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#667900 | #9514. 研心 | ANIG# | 50 | 3518ms | 117872kb | C++14 | 2.4kb | 2024-10-23 09:34:44 | 2024-10-23 09:34:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int N=4e5+5;
int n,m,l1[N],l2[N],zd1[N],zd2[N],res;
vector<int>q1[N],q2[N],mk1[N],mk2[N];
vector<ull>qh1[N],qh2[N],hh1[N],hh2[N];
ull pw[N];
ull h1(vector<ull>&h,int l,int r){
return h[r]-h[l-1]*pw[r-l+1];
}
ull h2(vector<ull>&h,int l,int r){
return h[l]-h[r+1]*pw[r-l+1];
}
int glh(vector<ull>&qh,vector<ull>&hh,int n){
int res=0;
for(int i=1;i<=n;i++){
int l=1,r=min(i,n-i+1);
while(l<r){
int mid=l+r+1>>1;
if(h1(qh,i-mid+1,i+mid-1)==h2(hh,i-mid+1,i+mid-1))l=mid;
else r=mid-1;
}
res=max(res,2*l-1);
}
return res;
}
int gets(vector<int>&q1,vector<int>&q2,int k){
int nw=q2.size()-1,res=0;
while(k>0&&nw>0&&q1[k]==q2[nw])k--,nw--,res++;
return res;
}
int solve(int a,int b){
int res=max(zd1[a],zd2[b]);
for(int i=1;i<=l1[a];i++){
if(!mk1[a][i])continue;
res=max(res,l1[a]-i+1+gets(q1[a],q2[b],i-1)*2);
}
for(int i=1;i<=l2[b];i++){
if(!mk2[b][i])continue;
res=max(res,l2[b]-i+1+gets(q2[b],q1[a],i-1)*2);
}
// if(a<=2)cout<<a<<" "<<b<<" "<<res<<" "<<zd1[a]<<endl;
return res;
}
signed main(){
// freopen("mirror1.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
pw[0]=1;
for(int i=1;i<N;i++)pw[i]=pw[i-1]*131;
for(int i=1;i<=n;i++){
string s;
cin>>s;
l1[i]=s.size();
q1[i].push_back(0);
for(auto c:s)q1[i].push_back(c-'a');
qh1[i].resize(q1[i].size());
hh1[i].resize(q1[i].size());
mk1[i].resize(q1[i].size());
for(int j=1;j<=l1[i];j++)qh1[i][j]=qh1[i][j-1]*131+q1[i][j]+1;
for(int j=l1[i];j>=1;j--)hh1[i][j]=hh1[i][j+1]*131+q1[i][j]+1;
for(int j=1;j<=l1[i];j++)if(l1[i]-j+1&1)mk1[i][j]=h1(qh1[i],j,l1[i])==h2(hh1[i],j,l1[i]);
zd1[i]=glh(qh1[i],hh1[i],l1[i]);
}
for(int i=1;i<=m;i++){
string s;
cin>>s;
l2[i]=s.size();
q2[i].push_back(0);
for(auto c:s)q2[i].push_back(c-'a');
reverse(q2[i].begin()+1,q2[i].end());
qh2[i].resize(q2[i].size());
hh2[i].resize(q2[i].size());
mk2[i].resize(q2[i].size());
for(int j=1;j<=l2[i];j++)qh2[i][j]=qh2[i][j-1]*131+q2[i][j]+1;
for(int j=l2[i];j>=1;j--)hh2[i][j]=hh2[i][j+1]*131+q2[i][j]+1;
for(int j=1;j<=l2[i];j++)if(l2[i]-j+1&1)mk2[i][j]=h1(qh2[i],j,l2[i])==h2(hh2[i],j,l2[i]);
zd2[i]=glh(qh2[i],hh2[i],l2[i]);
}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)res+=solve(i,j);
cout<<(res+n*m)/2;
}
詳細信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 7ms
memory: 88596kb
input:
10 100 aabaababaaaababbabaaaababaababbbaabbbaabaabaabbbaababaaababbaababababbbaababbbbbbbbaabbbbaabbbbbbbbaabaabbbaabbbbbabbbbbaabbbaabaa bbaaabaabbbbaaabaaaaabbbbbabaabbabbaabbaabbaabbabbababaabaabbaabbbbbbaaaabbbbabaaaabaaabbbabaaaaaabbaaaabbbabbbbbaaaabbabaababbaabbaaabbbbbbaaaabbbababaabbaaaba b...
output:
10468
result:
ok single line: '10468'
Test #2:
score: 20
Accepted
time: 18ms
memory: 89996kb
input:
10 100 abbacbbaabababcaabbaabbbabcaccabcabbabbbccaacabaabacccbacaaabbaaabbbaacaabbabcabbbcbacaaaaabaaaabaaacbbccbacacbbaaccacbabcbccacbaaacaaacccbabbaccacaaacaabbbccaaccbbabaabcbbcbcbb bccabcacbacccbcababaccccaaabbccacaccccabbaabbcacabaccabacbbbaaaabaabccbcaacaaccbcacabcbbbcccccabccbaababccccabcabab...
output:
6384
result:
ok single line: '6384'
Test #3:
score: 20
Accepted
time: 12ms
memory: 89748kb
input:
50 50 aaaaabbabbbbbaababbaaaababaababababbbbaabaaaaaaaabaabbaaabaaaabaaabaabbbabbbababbbbabbbabbaaababbabaabbabbabbabbaaababaaaaabbbbbbaabaabaabbbbbabaaababb abbabbbaabaaaaabababaabbabaabbbbab bababbbbaabaabbaabbbbaabaabbbaabbbbaaabbabbbaaabbbbaaabaabbaaaaaabbbabaaaaabbaabaabaaabaaababbbbbaaabbbbbba...
output:
21362
result:
ok single line: '21362'
Test #4:
score: 20
Accepted
time: 12ms
memory: 89780kb
input:
50 50 aababcabbbcbaacaaaaccababbacbbaaabcbaaccabbababbcccaacaaaacacbcbaaabaacabbbbbbaccaaacbbacaacacbcccbbacabbcbcbacababcbbacaccaacacbcccbababaccabccccbabaccababccccbcbabcabcabccaaccababcbccacbbaaaacc cbaccababccbaaacbccabbcccacacacaaaabaaababcacabaccbccacbcbaaaaabbacbbaccabba ccbcbcacbcaccabbbccaa...
output:
13421
result:
ok single line: '13421'
Test #5:
score: 20
Accepted
time: 58ms
memory: 90080kb
input:
1000 1000 a aabbab bbbbababbbba bb baaaaa ba a baa a bbaaaabaaaba ba a a a bbababbbbbb b aaabb bbbbbaabbabab bbaaa aaaa aa aaaaaababb a bbaba baaa aabbab babaab b aab bbbabb aaaabbbbbaaaaaa bbbbbbbaabab bb ab aaa aaababb babaaaabab aa aaabaaababa abbabaaaaabb bbaa abaabb baa abba aaaa abbbb aab b aa...
output:
3159935
result:
ok single line: '3159935'
Subtask #2:
score: 30
Accepted
Test #6:
score: 30
Accepted
time: 2364ms
memory: 117068kb
input:
1 10000 bcacacbcdadbcbccbdddaaddabcaccccbaabbcdcdaabdacccadacbbbabdaaacadacdccadcbdadadcaaabdbdbdcdcccbacbdbccacbdadcaaaacbabdadcacdcacadcadaabdaaabccccdcbcdbcadcaabbbaacaadaccdaccadbddcdbccbcddcaadcaadaadbbaadbcdbddbcbadbccbaddaacabcdccbadaddcadcbababccabcaadbcbdbcbbcdcbdbcdbdaaddbacddcabbbdccbddba...
output:
1160913325
result:
ok single line: '1160913325'
Test #7:
score: 30
Accepted
time: 261ms
memory: 114100kb
input:
1 1000 caaadbacdaaccbdcaccbdbddcdaccaaaaaccdccaadbadbcdccaacdadcccaddadcbacbbdcaadbbcdaddcadddccdbabccdadcaacabcabbbdbbbbdbbaaccddcdddcddddddbdbbadbddcbacdcdbdabcbbdbbaaadbdacaccdbaaabacbacabdaccaabaadddccbabacdbdddbdcadadcdccabaabbccbacddddcbcdbabaadaddbbdabadaccbdbaaabdadadaadabbdbadacacbdcbcbdccc...
output:
134272327
result:
ok single line: '134272327'
Test #8:
score: 30
Accepted
time: 2363ms
memory: 116672kb
input:
1 10000 bbcbcaacaaaacacbacacbaacbacbaababaacacbacbacbccaacbbacbbccababcaaaccabaaccbbbaaaabbababaacbbccabcaccaaccbacccaacabcaacacaccababbbbbcbacaaabbcbaccacaaaaabbacbbcbbcabccaabcabcabaabbbabbababbabcacbcaccabacaababbacccabbcaaacacccbcbcccbbbbaababbabcaaabaccccbbbabccabacbcbabccccaccbcccccbcccccccbbc...
output:
1375114968
result:
ok single line: '1375114968'
Test #9:
score: 30
Accepted
time: 2355ms
memory: 115108kb
input:
1 10000 cbaacaaaaccacaacbbcacabccbbabbababbababbacbababbcabcbacabbaaaacccacbbaaacacbacccbababaabccbbcabbbcaacbcbbbcbcbccccbabcacccccaabbbccacccacabccbcccbaaaccbbbacbaabbcbaabccccaabacabccaaccbbbaccbbcbcaabcaacbcbbcacbcbcabbacbababcbcabcbaabbbbbcccccbcacbabbcccccaacccbaccbaacbccbcababbabcbbccbbbbacab...
output:
1363955024
result:
ok single line: '1363955024'
Test #10:
score: 30
Accepted
time: 2367ms
memory: 115752kb
input:
1 10000 aacbabccacabcccbccbbcacbbcbcacbbcacbbcbcacacbaaabbbbccaabcbbccccaccccbbcbbcacbbcbbcacbbcbcacacbaaabbbbccaabcbbccccaccccbbcbcbbccccaccccbbbccccaccccbbcbcbbccccaccccbbcbaaccbbbbaaaaabbbbccaabcbbccccaccccbbcbcbbccccaccccbbbccccaccccbbcbcbbccccaccccbbcbaaccbbbbaaabcacacbcbbcacbbcacacbaaabbbbccaa...
output:
1951994915
result:
ok single line: '1951994915'
Test #11:
score: 30
Accepted
time: 2358ms
memory: 115612kb
input:
1 10000 bbaabbaaaabbbaaabbbaabaabaababbbbbabaabbababaaabbbbbbabbaaaabbbbbbaabababbbbabbaababbbbabaabaabaaabbabababbbbbaabababbaabbabbbababbbabaaaaabaaaaaaabaabaaabababbbabbabbaaaabababbbbabaabbaaababbaabbbbabbabbabbabbabaababaaaabbbaabbaababbabbbbaaaaaaaaaababbbbabbbabbaabbbbaaabaabbbbbaabbaababbaba...
output:
424739578
result:
ok single line: '424739578'
Subtask #3:
score: 0
Time Limit Exceeded
Test #12:
score: 20
Accepted
time: 310ms
memory: 115952kb
input:
100 1000 abbabbbbabbbbabaabaabbbbabaaabbbaabaabbabaabaabbaabbaabbababbabbababbbaabaabbaabbbabaabbbaaaabaaaabaababbaaaaaaaaabaabbaababbbbbbabbbabbbbababbbaaaaaabaaaabaaabbabbaaaaabbbabbabaabbabababbaaababbbaaaabbabbbabbabbabbbbbbabaabaabbbaabaaabbaabbabbbbaabbabaaabaabaabbbabbbbbabaababbbabababaabbba...
output:
1289287
result:
ok single line: '1289287'
Test #13:
score: 20
Accepted
time: 600ms
memory: 117004kb
input:
1000 1000 babbbabaabaaaabbbbbababaaabbaabbbbbabbaababbbbaaabbbbaaabbbababbaaaabaaabbbbbbbbaabbabbbabbabbaaabaabbbbbbbababaabbbbabaaabbaaaaabbbaababbaaaaabbbbaaaabbbaabaaababaaabbabbbabbabbbabbaabbabbbabaaaaaabaabbabbababbbbbabaaabbbbababbbaabbbaaabbababaababbbbbaaabbbabbabaaaababbbaabaaaabbbabaaabbb...
output:
10431998
result:
ok single line: '10431998'
Test #14:
score: 20
Accepted
time: 3518ms
memory: 117188kb
input:
1000 10000 babbababbbaaaaaaaaababbabbbababbbbbbbbabaaaaaabbaababbbbbbbaaaabbaaaaabbbbbbbababbabaaaaabbaaabaaaaaaabbbabbabbaaabbbabbbbababababbabbababbabbbbaabbbbaababbaababbababbbaaabbbbaaabaaaabababbbbaabaababbabbbaabbbbbabbbaaabaabaabbaabaaaaabbabbbbaaabbabbbaababbbaabaaaabbbababbbbbbbabababbaabab...
output:
94347164
result:
ok single line: '94347164'
Test #15:
score: 0
Time Limit Exceeded
input:
10000 10000 bbbabbaababbbbbababbbbaabbabaaaababbabbbabababaaaaaababbbaabaabbababbbbbaa b aaabbbbbbabbaabbbbbbaabaaababbbabbabaaabababbababaaabbaabaabaabbbbabb abbaabbaababbbabaabababaaaaaaaabaabbbb bbbbbabbaabbaaaabaabaababbbababbbbbaaaabbabbbabbaabbbabaaababababaabbaaaabaabbaaabbbaaaaaababababbbabb...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #17:
score: 30
Accepted
time: 304ms
memory: 115688kb
input:
100 1000 bcbccabbbabacabaabbccbaaabbbbcbbbaaaacaaabbccbababbacbbabbbaccccccccbccabcaacbbccbbbbcaaacabcccaccbaacccbcbaaaccbcaaaaaaaabccaaaacccbabacbcababbacbbbcaabaaacbbcaccbaccccbbcbacabaacbcaccacbcbcbbcbccccbbcacccaabbabcaabbacabaaacccbbcbccbabbcbccbcbbbabbaabacbccbacababbacbababbbaacccacbabcabcaba...
output:
833103
result:
ok single line: '833103'
Test #18:
score: 30
Accepted
time: 585ms
memory: 116652kb
input:
1000 1000 cacccababcaaccbaaabcbcabcbbccbcbcbbcacbbcabcaaccabcccaacabccaacaaaababbbbbcbbcbcbbbcacbaabccaccbaacaaacabbbcbcbaabbcccacaababbbabcaabbaabaabaabaabccaacccbabcbaacccbbbccaacbbacacacaacccbcbcbaccbccaaacabaacbcbaacbcbacaccbacbbcaccbabbbabbbaccccbbbcacccccaacbbaaaccacabaaacaccabacacbaaaaacbacab...
output:
6757759
result:
ok single line: '6757759'
Test #19:
score: 30
Accepted
time: 3334ms
memory: 117872kb
input:
1000 10000 cbacbccbcbbcccbbcccaacccbbbacbccaaaccabacaabacccbbbcbabcaacabbabbabcaaaabccbabcaaacaaabbbacccacabcacccaaababcacbaacaccbccbcaaaaaaaaccabbcaaaaabccacaacbccabacabcccaabbcaccbcabbccbabbbccaacbabcbacacabbaaaababbccbcbacbbbcaccaabacbcaabbaaacaacccaaabbbcabbbcccacacaccaacbccabccbcacbbbbbabcbabbc...
output:
61388196
result:
ok single line: '61388196'
Test #20:
score: 0
Time Limit Exceeded
input:
10000 10000 aababaaccbcbabaccbaccbcaaabbcbbbbacbcbababbccbccbbac cbcccccacaccabcbbbaaabcaaccabccccccbabacbbabbaaacbabccbcaacacbbbabbbbcbbcbcbaaccaccbabccabbbbbabcabcbcccababbcabaccbbccbaaacaabacbcbcbbabbcbaabcaccaaaccbbcacaaabcabacabccbaabbacabccacbabbaababb cacbcbabc caacccaabaaccbbbabaababbbbcbcac...