QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558483 | #8668. 回文路径 | huangkaicheng | 0 | 182ms | 30472kb | C++14 | 3.2kb | 2024-09-11 16:24:45 | 2024-09-11 16:24:45 |
Judging History
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%