QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558483#8668. 回文路径huangkaicheng0 182ms30472kbC++143.2kb2024-09-11 16:24:452024-09-11 16:24:45

Judging History

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

  • [2024-09-11 16:24:45]
  • 评测
  • 测评结果:0
  • 用时:182ms
  • 内存:30472kb
  • [2024-09-11 16:24:45]
  • 提交

answer

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

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

etnzscotdwydojaxcwbbxvfocelfjzffrxefjgsibnhxcrlwzsbcgwgqbdpdkupgtiwirxglhiskyfbhqckcdllrolrqniicpqfszdypymcdrikpxbpazpqdsjcjbrvgptngpdihbuzbnxingoelpnububanocqwkkcvffprssrjaiivalzpohxnkjreihjmzwoyepaxvffybydpixhiiyhxwnwrunuucnvhcujrjlvfolveqdpxifzwpaaspruzjviarxeimqutstewknffqagjudsvsbiwilxrjcrxcfrw...

result:

wrong answer 1st lines differ - expected: '6', found: 'etnzscotdwydojaxcwbbxvfocelfjz...modwnmcozzeyzeqergwpatsrxqwcclt'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 182ms
memory: 30472kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

ccgahacndscleparmbgiwkahfkmhaehbnghigjegjmeqtlteooodmsbgccgbooenbdiammglvtyicdsdqlliekbflkkcneswwkalwlymaalpgdjidajkdfiiedjabajdiddeobccvkrpqmeblqwebdblenlddfaobcejrkbotkabfrlmorjwpfefwcmdehnnjyvijaaeghonbaatmjfmksemakihbojospbwmaxddscfgadajbiioqqflqimupqingapidiajlhmkajjacmtpkcvhehaoijccbbpagcmfjhr...

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%