QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#761044#9522. A Simple String ProblemClarusAC ✓509ms74608kbC++204.8kb2024-11-18 20:42:242024-11-18 20:42:30

Judging History

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

  • [2024-11-18 20:42:30]
  • 评测
  • 测评结果:AC
  • 用时:509ms
  • 内存:74608kb
  • [2024-11-18 20:42:24]
  • 提交

answer

#include <bits/stdc++.h>

using LL = long long;

struct SA
{
    int n;
    std::vector<int> sa, rk, lc;

    SA(std::string s) : n(s.size()), sa(n), rk(n), lc(n - 1, -1)
    {
        std::iota(sa.begin(), sa.end(), 0);
        std::sort(sa.begin(), sa.end(), [&](int a, int b)
        {
            return s[a] < s[b];
        });
        rk[sa[0]] = 0;
        for (int i = 1; i < n; i++)
        {
            rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
        }
        std::vector<int> tmp, cnt(n);
        tmp.reserve(n);
        for (int k = 1; rk[sa[n - 1]] < n - 1; k *= 2)
        {
            tmp.clear();
            for (int i = 0; i < k; i++)
            {
                tmp.push_back(n - k + i);
            }
            for (auto i : sa)
            {
                if (i >= k)
                {
                    tmp.push_back(i - k);
                }
            }
            std::fill(cnt.begin(), cnt.end(), 0);
            for (int i = 0; i < n; i++)
            {
                cnt[rk[i]]++;
            }
            for (int i = 1; i < n; i++)
            {
                cnt[i] += cnt[i - 1];
            }
            for (int i = n - 1; i >= 0; i--)
            {
                sa[-- cnt[rk[tmp[i]]]] = tmp[i];
            }
            std::swap(rk, tmp);
            rk[sa[0]] = 0;
            for (int i = 1; i < n; i++)
            {
                rk[sa[i]] = rk[sa[i - 1]] + 
                            (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n || 
                            tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
            }
        }
        for (int i = 0, j = 0; i < n; i++)
        {
            if (rk[i] == 0)
            {
                j = 0;
            }
            else
            {
                for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j]; j++);
                lc[rk[i] - 1] = j;
            }
        }
    }
};

void chmax(int &a, int b)
{
    a = a > b ? a : b;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::string s, t;
    std::cin >> s >> t;

    s += " " + t;
    int m = s.size();

    SA s1(s), s2(std::string(s.rbegin(), s.rend()));
    
    int logm = std::__lg(m);
    std::vector st1(logm + 1, std::vector<int>(m));
    std::vector st2(logm + 1, std::vector<int>(m));
    st1[0] = s1.lc, st2[0] = s2.lc;

    for (int j = 0; j < logm; j++)
    {
        for (int i = 0; i + (2 << j) <= m; i++)
        {
            st1[j + 1][i] = std::min(st1[j][i], st1[j][i + (1 << j)]);
            st2[j + 1][i] = std::min(st2[j][i], st2[j][i + (1 << j)]);
        }
    }

    auto &sa1 = s1.sa, &sa2 = s2.sa;
    auto &rk1 = s1.rk, &rk2 = s2.rk;
    auto lcp = [&](int l, int r) -> int // [l, r)
    {
        l = rk1[l];
        r = rk1[r];
        assert(l != r);
        if (l > r)
        {
            std::swap(l, r);
        }
        int k = std::__lg(r - l);
        return std::min(st1[k][l], st1[k][r - (1 << k)]);
    };
    auto lcs = [&](int l, int r) -> int // [l, r)
    {
        l = rk2[m - 1 - l];
        r = rk2[m - 1 - r];
        assert(l != r);
        if (l > r)
        {
            std::swap(l, r);
        }
        int k = std::__lg(r - l);
        return std::min(st2[k][l], st2[k][r - (1 << k)]);
    };

    for (int d = n; d > 0; d--)
    {
        for (int i = 0; i + d < m; i += d)
        {
            int j = i + d;
            if (j <= n || i >= n)
            {
                int l = i, r = j;
                if (j <= n) { r += n; }
                if (i >= n) { l -= n; }
                int x = lcp(l, r) + lcs(l, r) - 1;
                int y = 0;
                if (r + lcp(l, r) < m)
                {
                    chmax(y, lcp(l + lcp(l, r) + n, r + lcp(l, r)));
                }
                if (l - lcs(l, r) >= 0)
                {
                    chmax(y, lcs(l - lcs(l, r), r - lcs(l, r) - n));
                }
                if (x + y >= d)
                {
                    std::cout << 2 * d << '\n';
                    return 0;
                }
            }
            int x = lcp(i, j) + lcs(i, j) - 1;
            int y = 0;
            if (i > n && i - lcs(i, j) - n >= 0)
            {
                chmax(y, lcs(i - lcs(i, j) - n, j - lcs(i, j)));
            }
            else if (j < n && j + lcp(i, j) + n < m)
            {
                chmax(y, lcp(i + lcp(i, j), j + lcp(i, j) + n));
            }
            if (x + y >= d)
            {
                std::cout << 2 * d << '\n';
                return 0;
            }
        }
    }
    std::cout << 0 << '\n';

    return 0;
}

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

详细

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 261ms
memory: 74372kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 253ms
memory: 74456kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 250ms
memory: 74420kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 509ms
memory: 74376kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 204ms
memory: 74608kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 216ms
memory: 74372kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 446ms
memory: 74324kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed