QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558271 | #8668. 回文路径 | huangkaicheng | 0 | 41ms | 17804kb | C++14 | 3.3kb | 2024-09-11 15:15:59 | 2024-09-11 15:16:00 |
Judging History
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%