QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#717613 | #9522. A Simple String Problem | _CLY_ | WA | 808ms | 19512kb | C++17 | 2.0kb | 2024-11-06 18:29:30 | 2024-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]
- 提交
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;
}
详细
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'