QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#688588#9522. A Simple String Problemwtz2333AC ✓854ms157312kbC++144.6kb2024-10-30 11:17:152024-11-06 21:49:14

Judging History

你现在查看的是测评时间为 2024-11-06 21:49:14 的历史记录

  • [2024-11-10 22:37:40]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:780ms
  • 内存:157608kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:14]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:854ms
  • 内存:157312kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-30 11:17:16]
  • 评测
  • 测评结果:100
  • 用时:991ms
  • 内存:155732kb
  • [2024-10-30 11:17:15]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
const int maxn = 2e6 + 7;
const int SIGMA_SIZE = 128;
struct SuffixArray{
    int sa[maxn], S[maxn], rnk[maxn], tax[maxn], tp[maxn], height[maxn];
    int h[22][maxn];
    int n;
    int m = SIGMA_SIZE;
    void SA(string s) {
        int n = s.size();
        s = '#' + s;
        int m = SIGMA_SIZE;
        memset(tax,0,sizeof tax);
        auto RadixSort = [&]() {
            for (int i = 0; i <= m; ++i) tax[i] = 0;
            for (int i = 1; i <= n; ++i) ++tax[rnk[i]];
            for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
            for (int i = n; i; --i) sa[tax[rnk[tp[i]]]--] = tp[i];
        };
        for (int i = 1; i <= n; ++i) {
            S[i] = s[i] - '0';
            tp[i] = i;
            rnk[i] = S[i];
        }
        RadixSort();
        for (int len = 1, p = 0; p != n; m = p, len <<= 1) {
            p = 0;
            for (int i = n - len + 1; i <= n; ++i) tp[++p] = i;
            for (int i = 1; i <= n; ++i) if (sa[i] > len) tp[++p] = sa[i] - len;
            RadixSort();
            std::swap(rnk, tp);
            p = 0;
            for (int i = 1; i <= n; ++i)
              rnk[sa[i]] = ((tp[sa[i]] == tp[sa[i-1]]) && (tp[sa[i] + len] == tp[sa[i-1] + len])) ? p : ++p;
        }
        for (int i = 1, p = 0; i <= n; ++i) {
            int pre = sa[rnk[i] - 1];
            if (p) --p;
            while (S[pre + p] == S[i + p]) ++p;
            h[0][rnk[i]] = height[rnk[i]] = p;
        }
        for (int i = 1; i <= 20; ++i) {
            memset(h[i], 0x3f, n * 4 + 4);
            for (int j = 1; j + (1 << i - 1) <= n; ++j)
                h[i][j] = min(h[i - 1][j], h[i - 1][j + (1 << i - 1)]);
        }
    }
    int Q(int l, int r) {
        if (l > r) swap(l, r);
        ++l;
        int k = __lg(r - l + 1);
        return min(h[k][l], h[k][r - (1 << k) + 1]);
    }
    int lcp(int i, int j) {
        if (i == j) return n - i + 1;
        return Q(rnk[i], rnk[j]);
    }
}sa;
int solve(int n,string s,string t) {
    string S = s,T = t;
    reverse(S.begin(),S.end());
    reverse(T.begin(),T.end());
    string tmp = s + '1' + '2' + S + '3' + t + T + '4';
    sa.SA(tmp);
    // cerr << tmp << endl;
    // cerr << s << "#\n";
    // cerr << "#" << t << "\n";
    // // 1 - n
    auto lcp = [&](int op1,int op2,int i,int j) {
        if(i > n || j > n || i < 1 || j < 1) return 0;
        if(op1) i += 2 * n;
        if(op2) j += 2 * n;
        int ans = sa.lcp(i,j);
        if(op1) ans = min(ans,3 * n - i + 1);
        else ans = min(ans,n - i + 1);
        if(op2) ans = min(ans,3 * n - j + 1);
        else ans = min(ans,n - j + 1);
        return ans;
    };
    auto lcs = [&](int op1,int op2,int i,int j) {
        if(i > n || j > n || i < 1 || j < 1) return 0;
        i = n - i + 1;
        j = n - j + 1;
        i += n;
        j += n;
        if(op1) i += 2 * n;
        if(op2) j += 2 * n;
        int ans = sa.lcp(i,j);
        if(op1) ans = min(ans,4 * n - i + 1);
        else ans = min(ans,2 * n - i + 1);
        if(op2) ans = min(ans,4 * n - j + 1);
        else ans = min(ans,2 * n - j + 1);
        return ans;
    };    
    int mx = 0;
    for(int x = 1;x <= n;x ++) {
        for(int y = 1;y + x - 1 <= n;y += x) {
            int l = y,r = y + x - 1;
            {
                int k = r + lcp(1,1,l,r + 1);
                int j = l - lcs(1,1,l - 1,r);
                int i = j - lcs(0,1,j - 1,j - 1 + x);
                if(k - i + 1 >= 2 * x) {
                    // cerr << x << " " << l << " " << r << endl;
                    mx = x;
                    break;
                }
            }
            {
                int t1 = lcp(0,1,l,r + 1);
                int k = t1 ? r + t1 + lcp(1,1,l + t1,r + t1 + 1) : r;
                int t2 = lcs(0,1,l - 1,r);
                int i = t2 ? l - t2 - lcs(0,0,l - t2 - 1,r - t2) : l;
                if(k - i + 1 >= 2 * x) {
                    // cerr << t1 << " " << t2 << endl;
                    // cerr << x << " " << l << " " << r << " " << i << " " << k << endl;
                    mx = x;
                    break;
                }
            }
        }
    }
    return mx;
    // return 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    n ++;
    string s,t,S,T;
    cin >> s >> t;
    S = s,T = t;
    reverse(S.begin(),S.end());
    reverse(T.begin(),T.end());
    // cout << solve(n,T,S) << endl;
    cout << max(solve(n,s,t),solve(n,T,S)) * 2 << "\n";
}
//  [    |  .    |    ] 
//  [    |       |    ]

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

详细

Test #1:

score: 100
Accepted
time: 9ms
memory: 73720kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 11ms
memory: 73260kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 3ms
memory: 72156kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 9ms
memory: 72336kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 15ms
memory: 72528kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 7ms
memory: 73536kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 854ms
memory: 155020kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 804ms
memory: 157312kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 817ms
memory: 154824kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 748ms
memory: 155516kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 680ms
memory: 154880kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 775ms
memory: 152592kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 452ms
memory: 155744kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 16ms
memory: 73156kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 11ms
memory: 72876kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 14ms
memory: 73316kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 12ms
memory: 72416kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 8ms
memory: 72928kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 14ms
memory: 73060kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 12ms
memory: 73080kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed