QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#560863#8668. 回文路径konyakest0 31ms7556kbC++173.1kb2024-09-12 18:26:312024-09-12 18:26:32

Judging History

你现在查看的是最新测评结果

  • [2024-09-12 18:26:32]
  • 评测
  • 测评结果:0
  • 用时:31ms
  • 内存:7556kb
  • [2024-09-12 18:26:31]
  • 提交

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,6) cerr<<a[i];
	cerr<<endl;
	F(i,1,6) cerr<<b[i];
	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: 3836kb

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: 31ms
memory: 7556kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

1

result:

wrong answer 1st lines differ - expected: '9', found: '1'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%