QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560856 | #8668. 回文路径 | konyakest | 0 | 30ms | 7920kb | C++17 | 3.0kb | 2024-09-12 18:24:45 | 2024-09-12 18:24:46 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i,j,k) for(auto i=j;i<=(decltype(i))k;i++)
#define x first
#define y second
#define exec(...) [&](){__VA_ARGS__}()
#define endl '\n'
#define os ostream
#define pb push_back
#define view(x) begin(x),end(x)
#define lambda [&]
using namespace std;
using ll=long long;
template<typename T>void ckmax(T& x,T y){x=max(x,y);}
template<typename T>void ckmin(T& x,T y){x=min(x,y);}
#ifdef DEBUG
template<typename T1,typename T2>os& operator<<(os& out,pair<T1,T2> x);
template<typename T,typename=decltype(T().begin()),typename=enable_if_t<!is_same_v<decay_t<T>,string>>>os& operator<<(os& out,T x){out<<"{";auto n=0u;for(auto i:x) out<<i<<(++n==x.size()?"":",");return out<<"}";}
template<typename ...T>os& operator<<(os& out,tuple<T...> x){return apply(lambda(T... x){out<<"{";auto n=0u;((out<<x<<(++n==sizeof...(T)?"":",")),...);out<<"}";},x),out;}
template<typename T1,typename T2>os& operator<<(os& out,pair<T1,T2> x){return out<<tuple(x);}
#define debug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = "<<std::make_tuple(__VA_ARGS__)<<endl
#else
#define debug(...) (void)0
#endif
const int maxn=1e5+5;
const size_t mod=1e16+61,base=137;
int n,ans;
size_t hsh[2][maxn],revhsh[2][maxn],pw[maxn];
char a[maxn],b[maxn];
size_t gethsh(size_t* hsh,int l,int r){
if(l==r+1) return 0;
return (hsh[r]-size_t(__int128(hsh[l-1])*pw[r-l+1]%mod)+mod)%mod;
}
size_t getrvhsh(bool op,int l,int r){return gethsh(revhsh[op],n-r+1,n-l+1);}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>(a+1)>>(b+1);
pw[0]=1;
F(i,1,n) pw[i]=pw[i-1]*base%mod;
F(i,1,n){
hsh[0][i]=(hsh[0][i-1]*base+a[i])%mod;
revhsh[0][i]=(revhsh[0][i-1]*base+a[n-i+1])%mod;
}
F(i,1,n){
hsh[1][i]=(hsh[1][i-1]*base+b[i])%mod;
revhsh[1][i]=(revhsh[1][i-1]*base+b[n-i+1])%mod;
}
debug(gethsh(hsh[0],1,2));
debug(getrvhsh(1,4,5));
F(i,1,n) if(gethsh(hsh[0],1,i)==getrvhsh(0,1,i)) ckmax(ans,i);
debug(ans);
F(i,1,(n+1)/2){
{
int l=0,r=i-1;
while(l<r){
int mid=(l+r+1)/2;
if(gethsh(hsh[1],i-mid,i-1)==getrvhsh(1,i,i+mid-1)) l=mid;
else r=mid-1;
}
debug(i,l);
if(gethsh(hsh[0],1,i-l)==getrvhsh(1,2*i-(i-l),2*i-1)) ckmax(ans,i*2);
}
{
int l=0,r=i-1;
while(l<r){
int mid=(l+r+1)/2;
if(gethsh(hsh[0],i-mid+1,i)==getrvhsh(0,i+1,i+mid)) l=mid;
else r=mid-1;
}
debug(i,l);
if(gethsh(hsh[0],1,i-l)==getrvhsh(1,2*i-(i-l),2*i-1)) ckmax(ans,i*2);
}
}
debug(ans);
F(i,1,(n+2)/2){
{
int l=0,r=i-2;
while(l<r){
int mid=(l+r+1)/2;
if(gethsh(hsh[1],i-mid-1,i-2)==getrvhsh(1,i,i+mid-1)) l=mid;
else r=mid-1;
}
debug(i,l);
if(gethsh(hsh[0],1,i-l-1)==getrvhsh(1,2*i-2-(i-l-1)+1,2*i-2)) ckmax(ans,i*2-1),debug(ans,i);
}
{
int l=0,r=i-2;
while(l<r){
int mid=(l+r+1)/2;
if(gethsh(hsh[0],i-mid+1-1,i-1)==getrvhsh(0,i+1,i+mid)) l=mid;
else r=mid-1;
}
debug(i,l);
if(gethsh(hsh[0],1,i-l-1)==getrvhsh(1,2*i-2-(i-l-1)+1,2*i-2)) ckmax(ans,i*2-1),debug(ans,i);
}
}
cout<<ans<<endl;
}
/*
*/
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: 5904kb
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: 30ms
memory: 7920kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
1
result:
wrong answer 1st lines differ - expected: '9', found: '1'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%