QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557679#8668. 回文路径Add_Catalyst0 29ms7888kbC++142.7kb2024-09-11 10:53:552024-09-11 10:53:55

Judging History

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

  • [2024-09-11 10:53:55]
  • 评测
  • 测评结果:0
  • 用时:29ms
  • 内存:7888kb
  • [2024-09-11 10:53:55]
  • 提交

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%