QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557600#8668. 回文路径Take_A_Single_60 8ms10800kbC++141.5kb2024-09-11 10:28:042024-09-11 10:28:05

Judging History

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

  • [2024-09-11 10:28:05]
  • 评测
  • 测评结果:0
  • 用时:8ms
  • 内存:10800kb
  • [2024-09-11 10:28:04]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define db double
#define maxn 1000005
#define mod 1000000007
#define fir first
#define sec second
#define pr pair<int,int>
#define mk make_pair
#define inf 10000000000000000
using namespace std;
inline int read()
{
    int SS=0,WW=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')WW=-1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        SS=(SS<<1)+(SS<<3)+(ch^48);
        ch=getchar();
    }
    return SS*WW;
}
inline void write(int XX)
{
    if(XX<0)putchar('-'),XX=-XX;
    if(XX>9)write(XX/10);
    putchar(XX% 10 + '0');
}
int n,hs1[maxn],hs2[maxn],bs=131,pw[maxn],ans,nxt[maxn];
char s1[maxn],s2[maxn],s[maxn];
int geths1(int l,int r)
{
	return hs1[r]-hs1[l-1]*pw[r-l+1];
}
int geths2(int l,int r)
{
	return hs2[r]-hs2[l-1]*pw[r-l+1];
}
bool ck1(int l,int r)
{
	int len=r-l+1>>1;
	if(geths1(l,l+len-1)==geths1(r-len+1,r))return true;
	return false;
}
bool ck2(int l,int r)
{
	int len=r-l+1>>1;
	if(geths2(l,l+len-1)==geths2(r-len+1,r))return true;
	return false;
}
bool ck(int l,int r)
{
	;
}
signed main()
{
	int l,r,mid;
	n=read(),cin>>s1+1>>s2+1,pw[0]=1;
	for(int i=1;i<=n;i++)hs1[i]=hs1[i-1]*bs+s1[i],pw[i]=pw[i-1]*bs;
	for(int i=1;i<=n;i++)hs2[i]=hs2[i-1]*bs+s2[i];
	for(int i=1;i<=n;i++)
	{
		l=i,r=n;
		while(l<=r)
		{
			int mid=l+r>>1;
			if(ck1(i,mid)||ck2(i,mid))ans=max(ans,mid-i+1),l=mid+1;
			else r=mid-1;
		}
	}
	write(ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7692kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

5

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 8ms
memory: 10800kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

7

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%