QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#699416#9522. A Simple String ProblemlrherAC ✓1079ms17924kbC++143.9kb2024-11-02 08:52:282024-11-02 08:52:28

Judging History

你现在查看的是测评时间为 2024-11-02 08:52:28 的历史记录

  • [2024-11-10 22:38:06]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1066ms
  • 内存:17736kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:46]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1088ms
  • 内存:18088kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-11-02 08:52:28]
  • 评测
  • 测评结果:100
  • 用时:1079ms
  • 内存:17924kb
  • [2024-11-02 08:52:28]
  • 提交

answer

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<string>
#include<bitset>
#include<vector>
#include<cstdio>
#include<random>
#include<complex>
#include<cstdlib>
#include<climits>
#include<iomanip>
#include<cstring>
#include<cassert>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
const long long _base=107374183;
int writetemp[30];
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;
    return x;
}
inline void write(long long x)
{
    int tot=(x==0);
    writetemp[1]=0;
    while(x) writetemp[++tot]=x%10,x/=10;
    while(tot) putchar(writetemp[tot--]+'0');
    putchar('\n');
    return ;
}
const int mod=1000000007,base=31;
int n,ans;
char a[1000010],b[1000010];
long long mul[1000010];
long long haa[1000010],hab[1000010];
long long pd(long long x)
{
    if(x>=mod) return x-mod;
    return x;
}
long long get_a(int l,int r)
{
    return pd(haa[r]-haa[l-1]*mul[r-l+1]%mod+mod);
}
long long get_b(int l,int r)
{
    return pd(hab[r]-hab[l-1]*mul[r-l+1]%mod+mod);
}
int solve(char *a,char *b)
{
    for(int i=1;i<=n;i++) haa[i]=(haa[i-1]*base+a[i]-'a')%mod;
    for(int i=1;i<=n;i++) hab[i]=(hab[i-1]*base+b[i]-'a')%mod;
    for(int k=n;k>=1;k--)
    {
        for(int now=k;now+k-1<=n;now+=k) if(get_a(now-k+1,now)==get_b(now,now+k-1)) return k+k;
        for(int now=k;now+k-1<=n;now+=k)
        {
            int nxt=now+k,nowlen=0;
            int l=0,r=k;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(get_a(now-mid+1,now)==get_a(nxt-mid+1,nxt)) l=mid;
                else r=mid-1;
            }
            now++,nxt++,nowlen=l;
            l=0,r=min(k,n-nxt+1);
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(get_a(now,now+mid-1)==get_a(nxt,nxt+mid-1)) l=mid;
                else r=mid-1;
            }
            now+=l,nxt+=l-1,nowlen+=l;
            l=0,r=min(k,n-nxt+1);
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(get_a(now,now+mid-1)==get_b(nxt,nxt+mid-1)) l=mid;
                else r=mid-1;
            }
            nowlen+=l;
            if(nowlen>=k) return k+k;
        }
        for(int now=k;now+k-1<=n;now+=k)
        {
            int nxt=now+k,nowlen=0;
            now++;
            int l=0,r=min(k,n-nxt+1);
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(get_a(now,now+mid-1)==get_b(nxt,nxt+mid-1)) l=mid;
                else r=mid-1;
            }
            now--,nxt--,nowlen=l;
            l=0,r=k;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(get_a(now-mid+1,now)==get_b(nxt-mid+1,nxt)) l=mid;
                else r=mid-1;
            }
            now-=l,nxt-=l-1,nowlen+=l;
            l=0,r=min(k,now);
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(get_a(now-mid+1,now)==get_a(nxt-mid+1,nxt)) l=mid;
                else r=mid-1;
            }
            nowlen+=l;
            if(nowlen>=k) return k+k;
        }
    }
    return 0;
}
int main()
{
    // freopen("s.out","r",stdin);
    // freopen("a.out","w",stdout);
    scanf("%d",&n),mul[0]=1;
    scanf("%s%s",a+1,b+1);
    for(int i=1;i<=n;i++) mul[i]=mul[i-1]*base%mod;
    ans=solve(a,b);
    for(int i=1;i<=(n>>1);i++) swap(a[i],a[n-i+1]),swap(b[i],b[n-i+1]);
    ans=max(ans,solve(b,a));
    printf("%d\n",ans);
    return 0;
}
/*
6
aaabab
aabbab
*/

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

详细

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 501ms
memory: 17924kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 499ms
memory: 17384kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 513ms
memory: 17216kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 1079ms
memory: 15004kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

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

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 39ms
memory: 17336kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 1005ms
memory: 16856kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed