QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#732747#9522. A Simple String Problemsz051AC ✓501ms11392kbC++202.2kb2024-11-10 15:44:562024-11-10 22:38:56

Judging History

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

  • [2024-11-10 22:38:56]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:501ms
  • 内存:11392kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-10 15:44:57]
  • 评测
  • 测评结果:100
  • 用时:491ms
  • 内存:10724kb
  • [2024-11-10 15:44:56]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector> 
#define int long long
using namespace std;

const int md=998244353,bas=131;
void read(int &x){
	x=0;
	char c=getchar();
	while(!('0'<=c && c<='9')){
		c=getchar();
	}
	while('0'<=c && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
}
int n,pw[600010],hsh[600010];
char s[600010];
int gethsh(int l,int r){
	if(l>r){
		return 0;
	}
	return (hsh[r]+(md-pw[r-l+1])*hsh[l-1])%md;
}
int getlcp(int i,int j,int upl){
	//printf("[LCP %lld %lld %lld]:",i,j,upl);
	int ql=0,qr=upl+1;
	while(ql<qr-1){
		int mid=(ql+qr)>>1;
		if(gethsh(i,i+mid-1)==gethsh(j,j+mid-1)){
			ql=mid;
		}else{
			qr=mid;
		}
	}
	//printf("[%lld]\n",ql);
	return ql;
}
int getlcs(int i,int j,int upl){
	//printf("[LCS %lld %lld %lld]:",i,j,upl);
	int ql=0,qr=upl+1;
	while(ql<qr-1){
		int mid=(ql+qr)>>1;
		if(gethsh(i-mid+1,i)==gethsh(j-mid+1,j)){
			ql=mid;
		}else{
			qr=mid;
		}
	}
	//printf("[%lld]\n",ql);
	return ql;
}
signed main(){
	pw[0]=1;
	for(int i=1;i<=400005;i++){
		pw[i]=pw[i-1]*bas%md;
	} 
	read(n);
	n++;
	scanf(" %s %s",s+1,s+n+2);
	s[n+1]='#';
	for(int i=1;i<=2*n;i++){
		hsh[i]=(hsh[i-1]*bas+s[i])%md;
	}
	//printf("[%lld %lld]",gethsh(1,3),gethsh(10,12));
	int res=0;
	for(int i=1;i<=n/2;i++){
		for(int j=i;j+i<=n;j+=i){
			int cl=getlcs(j,j+i,i),cr=getlcp(j+1,j+i+1,min(i-cl,n-j-i));
			if(j+2*i-cl>n){
				continue;
			} 
			if(cl+cr==i || gethsh(j+cr+1,j+i-cl)==gethsh(n+j+cr+1+i,n+j+i+i-cl)){
				res=i;
				break;
			}
		}
		if(res==i){
			continue;
		}
		for(int j=i;j+i<=n;j+=i){
			int cl=getlcs(n+j,n+j+i,i),cr=getlcp(n+j+1,n+j+i+1,min(i-cl,n-j-i));
			if(cl+cr==i || gethsh(j+cr-i+1,j-cl)==gethsh(n+j+cr+1,n+j+i-cl)){
				res=i;
				break;
			}
		}
		if(res==i){
			continue;
		}
		for(int j=i;j+i<=n;j+=i){
			int cl=getlcs(j,n+j+i,i),cr=getlcp(j+1,n+j+i+1,min(i-cl,n-j-i));
			if(cl+cr==i || gethsh(j+cr-i+1,j-cl)==gethsh(j+cr+1,j+i-cl)){
				res=i;
				break;
			}
			if(j+2*i-cl<=n && gethsh(n+j+cr+1,n+j+i-cl)==gethsh(n+j+cr+1+i,n+j+i+i-cl)){
				continue;
			} 
			
		}
	}
	printf("%lld",res*2);
	return 0;
}
/*
5
abcab
acabc
*/ 

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5580kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 5744kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 2ms
memory: 5580kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 2ms
memory: 5692kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 2ms
memory: 5572kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 7628kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 435ms
memory: 10132kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 434ms
memory: 11392kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 440ms
memory: 9780kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 489ms
memory: 10484kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 477ms
memory: 9788kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 501ms
memory: 11164kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 434ms
memory: 10836kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 3ms
memory: 7784kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 2ms
memory: 6024kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 0ms
memory: 5652kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 2ms
memory: 5780kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 3ms
memory: 7792kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 2ms
memory: 5584kb

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 2ms
memory: 5928kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 2ms
memory: 5696kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed