QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717613#9522. A Simple String Problem_CLY_WA 808ms19512kbC++172.0kb2024-11-06 18:29:302024-11-06 18:29:30

Judging History

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

  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-11-06 18:29:30]
  • 评测
  • 测评结果:WA
  • 用时:808ms
  • 内存:19512kb
  • [2024-11-06 18:29:30]
  • 提交

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 13131
#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) swap(x,y);
	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) swap(x,y);
	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);
	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;!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-t1),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,ls-(i+2*le)+2)>=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-t1),t3=LCS(i+le-1,i+2*le-1,le);
				if(t1+t2+t3>=le){
					f=1;
				}
			}
		}
		if(f){
			printf("%d\n",le*2); return 0;
		}
	}
	printf("0\n");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

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

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: -100
Wrong Answer
time: 808ms
memory: 19512kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

8

result:

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