QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#667900#9514. 研心ANIG#50 3518ms117872kbC++142.4kb2024-10-23 09:34:442024-10-23 09:34:44

Judging History

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

  • [2024-10-23 09:34:44]
  • 评测
  • 测评结果:50
  • 用时:3518ms
  • 内存:117872kb
  • [2024-10-23 09:34:44]
  • 提交

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

output:


result: