QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558271#8668. 回文路径huangkaicheng0 41ms17804kbC++143.3kb2024-09-11 15:15:592024-09-11 15:16:00

Judging History

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

  • [2024-09-11 15:16:00]
  • 评测
  • 测评结果:0
  • 用时:41ms
  • 内存:17804kb
  • [2024-09-11 15:15:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long maxn=1e5+5,base=131;
int n;
char c[3][maxn];
struct QQ{
	long long x,y;
	bool friend operator < (QQ x,QQ y){return x.x<y.x||(x.x==y.x&&x.y<y.y);}
	bool friend operator ==(QQ x,QQ y){return x.x==y.x&&x.y==y.y;}
};
const QQ mod={(long long)1e9+7,(long long)1e9+9};
QQ mi[maxn];
map<QQ,int> mp;
struct HAS{
	QQ zheng[maxn],fan[maxn];
	QQ H_zheng(int l,int r)
	{
		return {(zheng[r].x-zheng[l-1].x*mi[r-l+1].x%mod.x+mod.x)%mod.x,
				(zheng[r].y-zheng[l-1].y*mi[r-l+1].y%mod.y+mod.y)%mod.y};
	}
	QQ H_fan(int l,int r)
	{
		return {(fan[l].x-fan[r+1].x*mi[r-l+1].x%mod.x+mod.x)%mod.x,
				(fan[l].y-fan[r+1].y*mi[r-l+1].y%mod.y+mod.y)%mod.y};
	}
}ha[3];
int ans;
void XIA()//zhou zai xia
{
	mp.clear();
	QQ delta={0,0};
	for (int i=1;i<=n;i++)
	{
		mp[{(ha[1].H_fan(1,i).x-delta.x+mod.x)%mod.x,
			(ha[1].H_fan(1,i).y-delta.y+mod.y)%mod.y}]+=1;
		int len=i;
		if (i+len-1<=n)
		{
			if (mp.find({(ha[2].H_zheng(i,i+len-1).x-delta.x+mod.x)%mod.x,
						 (ha[2].H_zheng(i,i+len-1).y-delta.y+mod.y)%mod.y})!=mp.end())	ans=max(ans,len*2);//gui xia
		}
		
//		if (i+len<=n)
//		{
//			if (mp[(ha[2].H_zheng(i+1,i+len)-delta+mod)%mod]>0)	ans=max(ans,len*2+1);//zhong li
//		}
		
		delta={(delta.x+(long long)c[2][i]*mi[i].x)%mod.x,
			   (delta.y+(long long)c[2][i]*mi[i].y)%mod.y};
//		len=i+1;
//		if (i+len<=n)
//		{
//			if (mp[(ha[2].H_zheng(i+1,i+len)-delta+mod)%mod]>0)	ans=max(ans,len*2);//gui shang
//		}
	}
}
//void SHANG()//zhou zai shang
//{//chu li he shang mian lue you bu tong
//	mp.clear();
//	long long delta=0;
//	for (int i=n;i>=2;i--)
//	{
//		mp[(ha[2].H_zheng(i,n)-delta+mod)%mod]++;//ye ke bu shan?
//		//ci chu de shi ji yi yi: zhuan guo wan de hou zhui
//		int len=i;
//		long long zuo;
//		if (n-(2*len-1)>0)
//			zuo=(ha[1].H_fan(1,len)*mi[n-(2*len-1)]%mod+ha[2].H_zheng(2*len,n)-delta+mod)%mod;
//		else
//			zuo=(ha[1].H_fan(1,len)-delta+mod)%mod;
//		if (mp[zuo]>0)	ans=max(ans,len*2);//gui shang
//		
//		len=i-1;
//		if (n-(2*len)>0)
//			zuo=(ha[1].H_fan(1,len)*mi[n-(2*len)]%mod+ha[2].H_zheng(2*len+1,n)-delta+mod)%mod;
//		else
//			zuo=(ha[1].H_fan(1,len)-delta+mod)%mod;
//		if (mp[zuo]>0)	ans=max(ans,len*2+1);//zhong li
//		
//		delta=(delta+c[1][i]*mi[n-i+1])%mod;
//		
//		if (n-(2*len-1)>0)
//			zuo=(ha[1].H_fan(1,len)*mi[n-(2*len-1)]%mod+ha[2].H_zheng(2*len,n)-delta+mod)%mod;
//		else
//			zuo=(ha[1].H_fan(1,len)-delta+mod)%mod;
//		
//		if (mp[zuo]>0)	ans=max(ans,len*2);//gui xia
//	}
//}
int main()
{
	scanf("%d",&n);
	mi[0]={1,1};
	for (int i=1;i<=n;i++)	mi[i]={mi[i-1].x*base%mod.x,mi[i-1].y*base%mod.y};
	
	scanf("%s",c[1]+1);
	scanf("%s",c[2]+1);
	for (int i=1;i<=n;i++)
	{
		ha[1].zheng[i]={(ha[1].zheng[i-1].x*base+c[1][i])%mod.x,
						(ha[1].zheng[i-1].y*base+c[1][i])%mod.y};
		ha[2].zheng[i]={(ha[2].zheng[i-1].x*base+c[2][i])%mod.x,
						(ha[2].zheng[i-1].y*base+c[2][i])%mod.y};
	}
	for (int i=n;i>=1;i--)
	{
		ha[1].fan[i]={(ha[1].fan[i+1].x*base+c[1][i])%mod.x,
					  (ha[1].fan[i+1].y*base+c[1][i])%mod.y};
		ha[2].fan[i]={(ha[2].fan[i+1].x*base+c[2][i])%mod.x,
					  (ha[2].fan[i+1].y*base+c[2][i])%mod.y};
	}
	
	for (int i=1;i<=n;i++)
		if (ha[1].H_zheng(1,i)==ha[1].H_fan(1,i))	ans=max(ans,i);
	
	XIA();
//	SHANG();
	printf("%d",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 6028kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

3

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 41ms
memory: 17804kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

1

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%