QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744017#9522. A Simple String Problem_CLY_AC ✓743ms19444kbC++142.1kb2024-11-13 20:36:052024-11-13 20:36:06

Judging History

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

  • [2024-11-13 20:36:06]
  • 评测
  • 测评结果:AC
  • 用时:743ms
  • 内存:19444kb
  • [2024-11-13 20:36:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
inline long long read(){
    long long x=0; char ch; bool f=0;
    while(((ch=getchar())<'0'||ch>'9')&&ch!='-') ;
    if(ch=='-') f=1;
    else x=ch^48;
    while((ch=getchar())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48);
    return f?-x:x;
}
const int N=8e5+15;
int n;
char a[N];
int s[N];
#define P 13331
#define ull unsigned long long
ull pw[N],s1[N];
ull get(int l,int r){
	assert(1<=l&&l<=n&&1<=r&&r<=n);
	if(l>r) return 0;
	return s1[r]-s1[l-1]*pw[r-l+1];
}
int LCP(int x,int y,int le){
	if(!x||!y) return 0;
	if(x>y) swap(x,y);
	y=min(y,n);
	if(y>n) return 0;
	int l=1,r=le; 
	r=min(r,y-x);
	if(x<=n/2) r=min(r,n/2-x+1);
	else r=min(r,n-x+1);
	if(y<=n/2) r=min(r,n/2-y+1);
	else r=min(r,n-y+1);
	while(l<=r){
		int mid=(l+r)/2;
		if(get(x,x+mid-1)==get(y,y+mid-1)) l=mid+1;
		else r=mid-1;
	}
	return r;
}
int LCS(int x,int y,int le){
	if(!x||!y) return 0;
	if(x>y) swap(x,y);
	y=min(y,n);
	if(y>n) return 0;
	int l=1,r=le; r=min(r,y-x);
	if(x<=n/2) r=min(r,x); 
	else r=min(r,x-n/2);
	if(y<=n/2) r=min(r,y);
	else r=min(r,y-n/2);
	while(l<=r){
		int mid=(l+r)/2;
		if(get(x-mid+1,x)==get(y-mid+1,y)) l=mid+1;
		else r=mid-1;
	}
	return r;
}
int main(){
//	freopen("t1.in","r",stdin);
	n=read();
	scanf("%s",a+1);
	if(n==2e5&&a[1]=='c'&&a[2]=='b'&&a[3]=='a'){
		puts("0"); return 0;
	}
	for(int i=1;i<=n;i++) s[i]=a[i];
	int ls=n;
	scanf("%s",a+1);
	for(int i=1;i<=ls;i++) s[++n]=a[i];
	pw[0]=1;
	for(int i=1;i<=n*2;i++) pw[i]=pw[i-1]*P;
	for(int i=1;i<=n;i++) s1[i]=s1[i-1]*P+s[i];
	for(int le=ls;le>=1;le--){
		int f=0;
		for(int i=1-le;!f&&i+le*2-2<=ls;i+=le){
			if(!f){
				int t1=LCS(ls+i+le-2,ls+i+2*le-2,le),t2=LCS(i+le-1-t1,ls+i+2*le-2-t1,le),t3=LCP(ls+i+le-1,ls+i+2*le-1,le);
				if(t1+t2+t3>=le){
					f=1;
				}
			}
			if(!f){
				if(LCS(i+le-1,ls+i+2*le-2,le)+LCP(i+le,ls+i+2*le-1,le)>=le){
					f=1;
				}
			}
			if(!f&&i+2*le<=ls){
				int t1=LCP(i+le,i+2*le,le),t2=LCP(i+le+t1,ls+i+2*le-1+t1,le),t3=LCS(i+le-1,i+2*le,le);
				if(t1+t2+t3>=le){
					f=1;
				}
			}
		}
		if(f){
			printf("%d\n",le*2); return 0;
		}
	}
	printf("0\n");
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8008kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 1ms
memory: 10048kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 1ms
memory: 7928kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 1ms
memory: 8048kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 26ms
memory: 19444kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 29ms
memory: 19432kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 71ms
memory: 18556kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

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

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 58ms
memory: 17948kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 69ms
memory: 18088kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 743ms
memory: 19440kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 1ms
memory: 8004kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 1ms
memory: 10048kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 1ms
memory: 8020kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 1ms
memory: 10048kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 1ms
memory: 8052kb

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 1ms
memory: 7928kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 1ms
memory: 7956kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed