QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#668141#9514. 研心ANIG#0 1468ms579448kbC++144.3kb2024-10-23 11:48:002024-10-23 11:48:01

Judging History

This is the latest submission verdict.

  • [2024-10-23 11:48:01]
  • Judged
  • Verdict: 0
  • Time: 1468ms
  • Memory: 579448kb
  • [2024-10-23 11:48:00]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int N=8e5+5,T=70;
int n,m,l1[N],l2[N],zd1[N],zd2[N],res,idx,f[N];
vector<int>q1[N],q2[N],mk1[N],mk2[N],p[2][N],tmp[2][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;
}
struct msg{
	int op,bh,x;
}g[N];
vector<msg>jl[N];
int gets(msg x){
	if(!x.bh)return -1;
	if(x.op)return q2[x.bh][x.x];
	return q1[x.bh][x.x];
}
bool cmp(msg a,msg b){
	return gets(a)<gets(b);
}
ull h(msg x,int k){
	if(x.op)return h1(qh2[x.bh],x.x-k+1,x.x);
	return h1(qh1[x.bh],x.x-k+1,x.x);
}
void SA(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=l1[i];j++)g[++idx]={0,i,j};
		p[0][i].resize(q1[i].size());
		tmp[0][i].resize(q1[i].size());
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=l2[i];j++)g[++idx]={1,i,j};
		p[1][i].resize(q2[i].size());
		tmp[1][i].resize(q2[i].size());
	}
	sort(g+1,g+idx+1,cmp);
	int cnt=0;
	for(int i=1;i<=idx;i++){
		if(gets(g[i])!=gets(g[i-1]))cnt++;
		p[g[i].op][g[i].bh][g[i].x]=cnt;
	}
	for(int i=1;i<=20;i++){
		for(int j=1;j<=idx;j++){
			if(g[j].x-(1<<i-1)>0)jl[p[g[j].op][g[j].bh][g[j].x-(1<<i-1)]].push_back(g[j]);
			else jl[0].push_back(g[j]);
		}
		idx=0;
		for(int j=0;j<=cnt;j++){
			for(auto c:jl[j])g[++idx]=c;
			jl[j].clear();
		}
		for(int j=1;j<=idx;j++)jl[p[g[j].op][g[j].bh][g[j].x]].push_back(g[j]);
		idx=0;
		for(int j=0;j<=cnt;j++){
			for(auto c:jl[j])g[++idx]=c;
			jl[j].clear();
		}
		cnt=0;
		auto g1=[&](msg x){
			return p[x.op][x.bh][x.x];
		};
		auto g2=[&](msg x){
			if(x.x-(1<<i-1)<=0)return 0ll;
			return p[x.op][x.bh][x.x-(1<<i-1)];
		};
		for(int j=1;j<=idx;j++){
			if(j==1||g1(g[j])!=g1(g[j-1])||g2(g[j])!=g2(g[j-1]))cnt++;
			tmp[g[j].op][g[j].bh][g[j].x]=cnt;
		}
		for(int j=1;j<=n;j++)swap(tmp[0][j],p[0][j]);
		for(int j=1;j<=m;j++)swap(tmp[1][j],p[1][j]);
	}
	for(int i=1;i<=idx;i++)p[g[i].op][g[i].bh][g[i].x]=i;
	for(int i=1;i<idx;i++){
		int l=0,r=min(g[i].x,g[i+1].x);
		while(l<r){
			int mid=l+r+1>>1;
			if(h(g[i],mid)==h(g[i+1],mid))l=mid;
			else r=mid-1;
		}
		f[i]=l;
	}
}
int gets(int a,int b,int k1,int k2){
	if(!k1||!k2)return 0;
	int l=p[0][a][k1],r=p[1][b][k2],res=1e6;
	//cout<<a<<" "<<b<<" "<<k1<<" "<<k2<<" "<<l<<" "<<r<<endl;
	if(l>r)swap(l,r);
	for(int i=l;i<r;i++)res=min(res,f[i]);
	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(a,b,i-1,l2[b])*2);
	}
	for(int i=1;i<=l2[b];i++){
		if(!mk2[b][i])continue;
		res=max(res,l2[b]-i+1+gets(a,b,l1[a],i-1)*2);
	}
	return res;
}
signed main(){
//	freopen("mirror3.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]);
	}
	SA();
	return 0;
	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: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 43ms
memory: 257596kb

input:

10 100
aabaababaaaababbabaaaababaababbbaabbbaabaabaabbbaababaaababbaababababbbaababbbbbbbbaabbbbaabbbbbbbbaabaabbbaabbbbbabbbbbaabbbaabaa
bbaaabaabbbbaaabaaaaabbbbbabaabbabbaabbaabbaabbabbababaabaabbaabbbbbbaaaabbbbabaaaabaaabbbabaaaaaabbaaaabbbabbbbbaaaabbabaababbaabbaaabbbbbbaaaabbbababaabbaaaba
b...

output:


result:

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

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 1451ms
memory: 579448kb

input:

1 10000
bcacacbcdadbcbccbdddaaddabcaccccbaabbcdcdaabdacccadacbbbabdaaacadacdccadcbdadadcaaabdbdbdcdcccbacbdbccacbdadcaaaacbabdadcacdcacadcadaabdaaabccccdcbcdbcadcaabbbaacaadaccdaccadbddcdbccbcddcaadcaadaadbbaadbcdbddbcbadbccbaddaacabcdccbadaddcadcbababccabcaadbcbdbcbbcdcbdbcdbdaaddbacddcabbbdccbddba...

output:


result:

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

Subtask #3:

score: 0
Wrong Answer

Test #12:

score: 0
Wrong Answer
time: 1464ms
memory: 482272kb

input:

100 1000
abbabbbbabbbbabaabaabbbbabaaabbbaabaabbabaabaabbaabbaabbababbabbababbbaabaabbaabbbabaabbbaaaabaaaabaababbaaaaaaaaabaabbaababbbbbbabbbabbbbababbbaaaaaabaaaabaaabbabbaaaaabbbabbabaabbabababbaaababbbaaaabbabbbabbabbabbbbbbabaabaabbbaabaaabbaabbabbbbaabbabaaabaabaabbbabbbbbabaababbbabababaabbba...

output:


result:

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

Subtask #4:

score: 0
Wrong Answer

Test #17:

score: 0
Wrong Answer
time: 1468ms
memory: 467508kb

input:

100 1000
bcbccabbbabacabaabbccbaaabbbbcbbbaaaacaaabbccbababbacbbabbbaccccccccbccabcaacbbccbbbbcaaacabcccaccbaacccbcbaaaccbcaaaaaaaabccaaaacccbabacbcababbacbbbcaabaaacbbcaccbaccccbbcbacabaacbcaccacbcbcbbcbccccbbcacccaabbabcaabbacabaaacccbbcbccbabbcbccbcbbbabbaabacbccbacababbacbababbbaacccacbabcabcaba...

output:


result:

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