QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744017 | #9522. A Simple String Problem | _CLY_ | AC ✓ | 743ms | 19444kb | C++14 | 2.1kb | 2024-11-13 20:36:05 | 2024-11-13 20:36:06 |
Judging History
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