QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557600 | #8668. 回文路径 | Take_A_Single_6 | 0 | 8ms | 10800kb | C++14 | 1.5kb | 2024-09-11 10:28:04 | 2024-09-11 10:28:05 |
Judging History
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%