QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689013#9522. A Simple String ProblemFDUdululuAC ✓949ms85912kbC++205.3kb2024-10-30 14:53:012024-11-10 22:37:47

Judging History

你现在查看的是最新测评结果

  • [2024-11-10 22:37:47]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:949ms
  • 内存:85912kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:15]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1594ms
  • 内存:85984kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-30 14:53:02]
  • 评测
  • 测评结果:100
  • 用时:1037ms
  • 内存:85808kb
  • [2024-10-30 14:53:01]
  • 提交

answer

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int N = 4e5 + 5;  // |S|
const int M = 30;       // max ASCII(s_i)
const int K = 20;       // log N

int n;
string a, b;
char s[N], t[N];

struct SuffixArray {
    int n, m = M;
    int sa[N], rk[N], ht[N], tax[N], tmp[N];
    int st[N][K], lg[N];
    void init(int N) {
        n = N;
        for (int i = 0; i <= n + 1; i++) {
            sa[i] = rk[i] = ht[i] = 0;
            tax[i] = tmp[i] = 0;
        }
        for (int i = 0; i < K; i++)
            for (int j = 0; j <= n + 1; j++)
                st[i][j] = n;
        m = M;
        SA();
        get_ht();
        build();
    }
    void Qsort() {
        for (int i = 0; i <= m; i++)
            tax[i] = 0;
        for (int i = 1; i <= n; i++)
            tax[rk[i]]++;
        for (int i = 1; i <= m; i++)
            tax[i] += tax[i - 1];
        for (int i = n; i >= 1; i--)
            sa[tax[rk[tmp[i]]]--] = tmp[i];
    }
    int cmp(int x, int y, int w) {
        return (tmp[x] == tmp[y] && tmp[x + w] == tmp[y + w]);
    }
    void SA() {
        for (int i = 1; i <= n; i++) {
            rk[i] = s[i] - 'a' + 1;
            tmp[i] = i;
        }
        Qsort();
        for (int w = 1; w <= n; w <<= 1) {
            int p = 0;
            for (int i = n - w + 1; i <= n; i++)
                tmp[++p] = i;
            for (int i = 1; i <= n; i++)
                if (sa[i] > w)
                    tmp[++p] = sa[i] - w;
            Qsort();
            swap(tmp, rk);
            rk[sa[1]] = p = 1;
            for (int i = 2; i <= n; i++)
                rk[sa[i]] = cmp(sa[i - 1], sa[i], w) ? p : ++p;
            if (p == n)
                break;
            m = p;
        }
    }
    void get_ht() {  // ht[i] = lcp(sa[i], sa[i - 1])
        for (int i = 1, k = 0; i <= n; i++) {
            if (k)
                --k;
            // 多测记得防越界
            // 或者 s[] 开两倍空间,清空后一半
            // while ((i + k <= n && sa[rk[i] - 1] + k <= n) && s[i + k] == s[sa[rk[i] - 1] + k])
            //	 k++;
            while (s[i + k] == s[sa[rk[i] - 1] + k])
                k++;
            ht[rk[i]] = k;
        }
    }
    void build() {
        for (int i = 2; i <= n; i++)  // index starts with 2
            lg[i] = lg[i >> 1] + 1;
        for (int i = 1; i <= n; i++)
            st[i][0] = ht[i];
        for (int i = 1; i < K; i++)
            for (int j = 1; j + (1 << i) - 1 <= n; j++)
                st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
    }
    int query(int L, int R) {  // lcp(s[i,n],s[j,n])
        if (L < 1 || L > n || R < 1 || R > n)
            return 0;
        int l, r;
        l = min(rk[L], rk[R]) + 1;
        r = max(rk[L], rk[R]);
        int t = lg[r - l + 1];
        return min(st[l][t], st[r - (1 << t) + 1][t]);
    }
} f, g;

void solve() {
    cin >> n;
    cin >> a >> b;
    a = " " + a, b = " " + b;

    s[n + 1] = '{';
    for (int i = 1; i <= n; i++)
        s[i] = a[i], s[n + 1 + i] = b[i];
    for (int i = 1; i <= 2 * n + 1; i++)
        t[i] = s[i];
    f.init(2 * n + 1);
    reverse(s + 1, s + 2 * n + 1 + 1);
    g.init(2 * n + 1);

    int ans = 0;
    for (int len = 1; len <= n; len++) {
        for (int i = 1; i <= n; i += len) {
            int pre, suf, nxtsuf, nxtpre;

            // a
            pre = g.query(2 * n + 1 - i + 1, 2 * n + 1 - (i + len) + 1);
            suf = f.query(i, i + len);
            if (pre + suf > len)
                ans = max(ans, 2 * len);

            // b
            pre = g.query(2 * n + 1 - (n + 1 + i) + 1, 2 * n + 1 - (n + 1 + i + len) + 1);
            suf = f.query(n + 1 + i, n + 1 + i + len);
            if (pre + suf > len)
                ans = max(ans, 2 * len);

            // a + b
            // aa
            pre = g.query(2 * n + 1 - (i) + 1, 2 * n + 1 - (i + len) + 1);
            suf = f.query(i, i + len);
            nxtsuf = f.query((i + suf), n + 1 + (i + len + suf - 1));
            if (pre + suf + nxtsuf > len)
                ans = max(ans, 2 * len);
            // ab
            pre = g.query(2 * n + 1 - (i) + 1, 2 * n + 1 - (n + 1 + i + len - 1) + 1);
            suf = f.query(i, n + 1 + (i + len - 1));
            nxtpre = g.query(2 * n + 1 - (i - pre) + 1, 2 * n + 1 - (i + len - 1 - pre + 1) + 1);
            nxtsuf = f.query(n + 1 + (i + suf - 1), n + 1 + (i + len - 1 + suf));
            if (pre + suf + max(nxtsuf, nxtpre) > len)
                ans = max(ans, 2 * len);
            // bb
            pre = g.query(2 * n + 1 - (n + 1 + i + len - 1) + 1, 2 * n + 1 - (n + 1 + i + 2 * len - 1) + 1);
            suf = f.query(n + 1 + i + len - 1, n + 1 + (i + 2 * len - 1));
            nxtpre = g.query(2 * n + 1 - (i + len - 1 - pre + 1) + 1, 2 * n + 1 - (n + 1 + i + 2 * len - 1 - pre) + 1);
            if (pre + suf + nxtpre > len)
                ans = max(ans, 2 * len);
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

/*

5
abcab
acabc

6
babbaa
babaaa

2
ne
fu


*/

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 22376kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 4ms
memory: 22456kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 5ms
memory: 22076kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 4ms
memory: 22232kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 907ms
memory: 85680kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 886ms
memory: 85912kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 896ms
memory: 85872kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 687ms
memory: 85612kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 737ms
memory: 85668kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 949ms
memory: 85768kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 738ms
memory: 85748kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 2ms
memory: 22076kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 4ms
memory: 22044kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 5ms
memory: 22020kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 5ms
memory: 22268kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed