QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#703880#9522. A Simple String Problem1e11AC ✓305ms79916kbC++204.6kb2024-11-02 18:46:112024-11-10 22:38:11

Judging History

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

  • [2024-11-10 22:38:11]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:305ms
  • 内存:79916kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:49]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:455ms
  • 内存:79944kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-11-02 18:46:14]
  • 评测
  • 测评结果:100
  • 用时:308ms
  • 内存:79956kb
  • [2024-11-02 18:46:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = int64_t;

#define all(v) begin(v), end(v)

auto sais(const auto &s) {
    const int n = (int)s.size(), z = ranges::max(s) + 1;
    if (n == 1) return vector{0};
    vector<int> c(z); for (int x : s) ++c[x];
    partial_sum(all(c), begin(c));
    vector<int> sa(n); auto I = views::iota(0, n);
    vector<bool> t(n); t[n - 1] = true;
    for (int i = n - 2; i >= 0; --i)
        t[i] = (s[i] == s[i + 1] ? t[i + 1] : s[i] < s[i + 1]);
    auto is_lms = views::filter([&t](int x) {
        return x && t[x] && !t[x - 1]; });
    auto induce = [&] {
        for (auto x = c; int y : sa)
            if (y--) if (!t[y]) sa[x[s[y] - 1]++] = y;
        for (auto x = c; int y : sa | views::reverse)
            if (y--) if (t[y]) sa[--x[s[y]]] = y;
    };
    vector<int> lms, q(n); lms.reserve(n);
    for (auto x = c; int i : I | is_lms) {
        q[i] = int(lms.size());
        lms.push_back(sa[--x[s[i]]] = i);
    }
    induce(); vector<int> ns(lms.size());
    for (int j = -1, nz = 0; int i : sa | is_lms) {
        if (j >= 0) {
            int len = min({n - i, n - j, lms[q[i] + 1] - i});
            ns[q[i]] = nz += lexicographical_compare(begin(s) + j, begin(s) + j + len, begin(s) + i, begin(s) + i + len);
        }
        j = i;
    }
    ranges::fill(sa, 0); auto nsa = sais(ns);
    for (auto x = c; int y : nsa | views::reverse)
        y = lms[y], sa[--x[s[y]]] = y;
    return induce(), sa;
}
struct Suffix {
    int n;
    vector<int> sa, hi, rev;
    Suffix(const auto &s) : n(int(s.size())), hi(n), rev(n) {
        vector<int> _s(n + 1);
        copy(all(s), begin(_s));
        sa = sais(_s); sa.erase(sa.begin());
        for (int i = 0; i < n; ++i) rev[sa[i]] = i;
        for (int i = 0, h = 0; i < n; ++i) {
            if (!rev[i]) { h = 0; continue; }
            for (int j = sa[rev[i] - 1]; i + h < n && j + h < n && s[i + h] == s[j + h];) ++h;
            hi[rev[i]] = h ? h-- : 0;
        }
    }
};

template <int LG = 20> struct SparseTableSA : Suffix {
    array<vector<int>, LG> mn;
    SparseTableSA(const auto &s) : Suffix(s), mn{hi} {
        for (int l = 0; l + 1 < LG; l++) { mn[l + 1].resize(n);
            for (int i = 0, len = 1 << l; i + len < n; i++)
                mn[l + 1][i] = min(mn[l][i], mn[l][i + len]);
        }
    }
    int lcp(int a, int b) {
        if (a == b) return n - a;
        a = rev[a] + 1, b = rev[b] + 1;
        if (a > b) swap(a, b);
        const int lg = __lg(b - a);
        return min(mn[lg][a], mn[lg][b - (1 << lg)]);
    }
    pair<int, int> get_range(int x, int len) {
        int a = rev[x] + 1, b = rev[x] + 1;
        for (int l = LG - 1; l >= 0; l--) {
            const int s = 1 << l;
            if (a + s <= n && mn[l][a] >= len) a += s;
            if (b - s >= 0 && mn[l][b - s] >= len) b -= s;
        }
        return {b - 1, a};
    }
};

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;

    string S, T;
    cin >> S >> T;
    S = S + '$';
    T = '%' + T;
    ++n;

    auto rS = S, rT = T;
    reverse(all(rS));
    reverse(all(rT));

    auto F = '!' + S + '#' + T + '@';
    SparseTableSA sa('!' + S + '#' + T + '@');
    SparseTableSA rsa('!' + rS + '#' + rT + '@');

    auto OS = 1;
    auto OT = n + 2;

    for (int len = n; len >= 1; len--) {
        auto ok = [len] {
            cout << len * 2 << '\n';
            exit(0);
        };
        for (int i = 0; i + len < n; i += len) {
            int a = i, b = i + len;
            {
                int x = sa.lcp(a + OS, b + OT);
                int y = rsa.lcp(n - a + OS, n - b + OT);
                x += sa.lcp(a + x + OT, b + x + OT);
                if (x + y >= len)
                    ok();
            }
            {
                int x = sa.lcp(a + OS, b + OT);
                int y = rsa.lcp(n - a + OS, n - b + OT);
                y += rsa.lcp(n - (a - y) + OS, n - (b - y) + OS);
                if (x + y >= len)
                    ok();
            }
            {
                int x = sa.lcp(a + OT, b + OT);
                int y = rsa.lcp(n - a + OT, n - b + OT);
                y += rsa.lcp(n - (a - y) + OS, n - (b - y) + OT);
                if (x + y >= len)
                    ok();
            }
            {
                int x = sa.lcp(a + OS, b + OS);
                int y = rsa.lcp(n - a + OS, n - b + OS);
                x += sa.lcp(a + x + OS, b + x + OT);
                if (x + y >= len)
                    ok();
            }
        }
    }

    cout << 0 << '\n';
}

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

详细

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 83ms
memory: 78572kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 84ms
memory: 78396kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 111ms
memory: 78676kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 219ms
memory: 77368kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 63ms
memory: 78552kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 81ms
memory: 79916kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 305ms
memory: 78360kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed