QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557679 | #8668. 回文路径 | Add_Catalyst | 0 | 29ms | 7888kb | C++14 | 2.7kb | 2024-09-11 10:53:55 | 2024-09-11 10:53:55 |
Judging History
answer
#define Plus_Cat
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define ul unsigned long long
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define FOR(i,a,b) for(int i=(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i=(a);i>=(int)(b);--i)
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~(i);(i)=(g)[(i)].nxt,(y)=(g)[(i)].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=1e5+10,B=13331;
int n,ans;
int P[N][2];
string s,t;
namespace Hashs{
ul pw[N];
struct Hash{
ul h[N][2];
void Constr(const string &s){
FOR(i,1,s.size())h[i][0]=h[i-1][0]*B+s[i-1];
DOR(i,s.size(),1)h[i][1]=h[i+1][1]*B+s[i-1];
}
template<bool ty>ul Query(int l,int r){
return !ty?h[r][ty]-h[l-1][ty]*pw[r-l+1]:h[l][ty]-h[r+1][ty]*pw[r-l+1];
}
}S,T;
void Init(){
pw[0]=1;
FOR(i,1,N-5)pw[i]=pw[i-1]*B;
}
}using namespace Hashs;
signed main(){
#ifndef Plus_Cat
freopen("FILEname.in","r",stdin),freopen("FILEname.out","w",stdout);
#endif
cin>>n>>s>>t,Init(),S.Constr(s),T.Constr(t);
FOR(i,1,n){
int cur=0;
for(int l=1,r=min(i-1,n-i),mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
S.Query<1>(i-mid,i)==S.Query<0>(i,i+mid)?cur=mid,l=mid+1:r=mid-1;
int L=i-cur,R=i+cur;
cur=0;
for(int l=1,r=min(L-1,n-R+1),mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
S.Query<1>(L-mid,L-1)==T.Query<0>(R,R+mid-1)?cur=mid,l=mid+1:r=mid-1;
tomax(ans,(R-L+1)+2*cur);
}
FOR(i,1,n-1){
int cur=0;
for(int l=1,r=min(i,n-i),mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
S.Query<1>(i-mid+1,i)==S.Query<0>(i+1,i+mid)?cur=mid,l=mid+1:r=mid-1;
int L=i-cur,R=i+cur;
cur=0;
for(int l=1,r=min(L-1,n-R+1),mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
S.Query<1>(L-mid,L-1)==T.Query<0>(R,R+mid-1)?cur=mid,l=mid+1:r=mid-1;
tomax(ans,(R-L+1)+2*cur);
}
FOR(i,1,n){
int cur=0;
for(int l=1,r=min(i-1,n-i),mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
T.Query<1>(i-mid,i)==T.Query<0>(i,i+mid)?cur=mid,l=mid+1:r=mid-1;
int L=i-cur,R=i+1+cur;
cur=0;
for(int l=1,r=min(L-1,n-R+1),mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
S.Query<1>(L-mid+1,L)==T.Query<0>(R+1,R+mid)?cur=mid,l=mid+1:r=mid-1;
tomax(ans,(R-L+1)+2*cur);
}
FOR(i,1,n-1){
int cur=0;
for(int l=1,r=min(i,n-i),mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
T.Query<1>(i-mid+1,i)==T.Query<0>(i+1,i+mid)?cur=mid,l=mid+1:r=mid-1;
int L=i-cur,R=i+1+cur;
cur=0;
for(int l=1,r=min(L-1,n-R+1),mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
S.Query<1>(L-mid+1,L)==T.Query<0>(R+1,R+mid)?cur=mid,l=mid+1:r=mid-1;
tomax(ans,(R-L+1)+2*cur);
}
cout<<ans<<endl;
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: 5808kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
7
result:
wrong answer 1st lines differ - expected: '6', found: '7'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 29ms
memory: 7888kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
10
result:
wrong answer 1st lines differ - expected: '9', found: '10'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%