QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561373#8668. 回文路径hhiron0 20ms14420kbC++141.3kb2024-09-12 22:03:112024-09-12 22:03:11

Judging History

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

  • [2024-09-12 22:03:11]
  • 评测
  • 测评结果:0
  • 用时:20ms
  • 内存:14420kb
  • [2024-09-12 22:03:11]
  • 提交

answer

#include<bits/stdc++.h>
#define INF 0x7fffffff
#define int long long
#define ull unsigned long long
typedef long long ll;
using namespace std;
//const int MOD=547567998244353;
const int N=5e5+5;
int n,l,r,len[N];
ull po[N];
ull has1l[N],has1r[N],has2l[N],has2r[N];
string s1,s2;
ull gethash(int x,int y,ull *a){
	return (a[y]-a[x]*po[abs(y-x)]);
}
int ans=0;
void solve(){
	for(int i=1;i<=n;i++) has1l[i]=(has1l[i-1]*131+s1[i]);
	for(int i=1;i<=n;i++) has2l[i]=(has2l[i-1]*131+s2[i]);
	for(int i=n;i>=1;i--) has1r[i]=(has1r[i+1]*131+s1[i]);
	for(int i=n;i>=1;i--) has2r[i]=(has2r[i+1]*131+s2[i]);
//	cout<<s1<<endl;
	for(int i=1;i<=n;i++){
		int l=0,r=min(n-i,i-1);
		while(r-l>1){
			int mid=(l+r)>>1;
			if(gethash(i-mid,i+mid,has1l)==gethash(i+mid,i-mid,has1r)) l=mid;
			else r=mid;
		}int poil=i-r-1,poir=i+r;
		ans=max(ans,l*2+1);
		l=0,r=min(poil-1,n-poir);
		if(s1[poil]!=s2[poir]) continue;
//		while(r-l>1){
//			int mid=(l+r)>>1;
//			if(gethash(mid))
//		}
	}
}
signed main(){
	cin>>n>>s1>>s2;
	s1=" "+s1; s2=" "+s2;
	po[0]=1;
	for(int i=1;i<=n;i++) po[i]=po[i-1]*131;
	solve();
	swap(s1,s2);
	for(int i=1;i<=n/2;i++) swap(s1[i],s1[n-i+1]);
	for(int i=1;i<=n/2;i++) swap(s2[i],s2[n-i+1]);
	solve();
	printf("%lld",ans);
	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: 5852kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

5

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 20
Accepted
time: 19ms
memory: 9128kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 20
Accepted
time: 20ms
memory: 14420kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 20
Accepted
time: 19ms
memory: 12700kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

11

result:

ok single line: '11'

Test #14:

score: 20
Accepted
time: 11ms
memory: 9132kb

input:

99999
chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...

output:

9

result:

ok single line: '9'

Test #15:

score: 0
Wrong Answer
time: 13ms
memory: 9464kb

input:

99999
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

99997

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%