QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#679263 | #9522. A Simple String Problem | ucup-team5052# | AC ✓ | 413ms | 79788kb | C++14 | 2.7kb | 2024-10-26 17:14:52 | 2024-11-10 22:36:42 |
Judging History
你现在查看的是最新测评结果
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-28 15:17:17]
- hack成功,自动添加数据
- (/hack/1080)
- [2024-10-28 14:28:57]
- hack成功,自动添加数据
- (/hack/1079)
- [2024-10-27 18:36:42]
- hack成功,自动添加数据
- (/hack/1075)
- [2024-10-26 17:14:52]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
int n,buc[800010],sa[800010],rk[800010],ht[20][800010],tmp[800010];
char s[200010],t[200010],S[800010];
void get_sa(int n,char *s)
{
for(int i=1;i<=n;i++) buc[s[i]-'a']++;
for(int i=1;i<=40;i++) buc[i]+=buc[i-1];
for(int i=n;i>=1;i--) sa[buc[s[i]-'a']--]=i;
for(int i=1;i<=n;i++) rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]);
fill(buc,buc+41,0);
for(int k=1;k<n;k<<=1)
{
int tot=0;
for(int i=n-k+1;i<=n;i++) tmp[++tot]=i;
for(int i=1;i<=n;i++)
if(sa[i]>k) tmp[++tot]=sa[i]-k;
for(int i=1;i<=n;i++) buc[rk[i]]++;
for(int i=1;i<=n;i++) buc[i]+=buc[i-1];
for(int i=n;i>=1;i--) sa[buc[rk[tmp[i]]]--]=tmp[i];
fill(buc+1,buc+n+1,0);
for(int i=1;i<=n;i++) tmp[sa[i]]=tmp[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]] || rk[sa[i]+k]!=rk[sa[i-1]+k]);
move(tmp+1,tmp+n+1,rk+1);
if(rk[sa[n]]>=n) break;
}
for(int i=1,j=0;i<=n;i++)
{
while(s[i+j]==s[sa[rk[i]+1]+j]) j++;
ht[0][rk[i]]=j;
if(j) j--;
}
for(int i=1;i<=19;i++)
for(int j=1;j+(1<<i)-1<n;j++)
ht[i][j]=min(ht[i-1][j],ht[i-1][j+(1<<(i-1))]);
}
int lcp(int i,int j)
{
i=rk[i];j=rk[j];
if(i>j) swap(i,j);
int k=__lg(j-i);
return min(ht[k][i],ht[k][j-(1<<k)]);
}
int lcp_ss(int i,int j)
{
if(i>n || j>n) return 0;
return lcp(i,j);
}
int lcp_st(int i,int j)
{
if(i>n || j>n) return 0;
return lcp(i,j+2*(n+1));
}
int lcp_tt(int i,int j)
{
if(i>n || j>n) return 0;
return lcp(i+2*(n+1),j+2*(n+1));
}
int lcs_ss(int i,int j)
{
if(i<1 || j<1) return 0;
i=n-i+1;j=n-j+1;
return lcp(i+n+1,j+n+1);
}
int lcs_st(int i,int j)
{
if(i<1 || j<1) return 0;
i=n-i+1;j=n-j+1;
return lcp(i+n+1,j+3*(n+1));
}
int lcs_tt(int i,int j)
{
if(i<1 || j<1) return 0;
i=n-i+1;j=n-j+1;
return lcp(i+3*(n+1),j+3*(n+1));
}
int main() {
std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int m=0;
cin>>n>>s+1>>t+1;
for(int i=1;i<=n;i++) S[++m]=s[i];
S[++m]='z'+1;
for(int i=1;i<=n;i++) S[++m]=s[n-i+1];
S[++m]='z'+2;
for(int i=1;i<=n;i++) S[++m]=t[i];
S[++m]='z'+3;
for(int i=1;i<=n;i++) S[++m]=t[n-i+1];
get_sa(m,S);
for(int k=(n+1)/2;k>=1;k--)
{
bool ok=0;
for(int i=1;i+k<=n+1;i+=k)
{
int j=i+k,l1=lcs_ss(i-1,j-1),l2=lcp_ss(i,j);
if(l1+l2>=k) ok=1;
else
{
int l3=lcp_st(i+l2,j+l2-1);
if(l1+l2+l3>=k) ok=1;
}
if(ok) break;
l1=lcp_tt(i,j);l2=lcs_tt(i-1,j-1);
if(l1+l2>=k) ok=1;
else
{
int l3=lcs_st(i-l2,j-l2-1);
if(l1+l2+l3>=k) ok=1;
}
if(ok) break;
l1=lcs_st(i-1,j-2);l2=lcp_st(i,j-1);
int l3=lcs_ss(i-l1-1,j-l1-1),l4=lcp_tt(i+l2-1,j+l2-1);
if(l1+l2+max(l3,l4)>=k) ok=1;
if(ok) break;
}
if(ok)
{
cout<<2*k<<endl;
return 0;
}
}
cout<<0<<endl;
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18008kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 3ms
memory: 20060kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 15956kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 2ms
memory: 20112kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 17948kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 17952kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 236ms
memory: 79788kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 223ms
memory: 78536kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 233ms
memory: 79068kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 413ms
memory: 78060kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 186ms
memory: 78512kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 198ms
memory: 78724kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 310ms
memory: 79328kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 19996kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 22024kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 22160kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 22080kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 3ms
memory: 20036kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 13928kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 26216kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 24152kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed