QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760675#9522. A Simple String ProblemClarusWA 490ms74648kbC++204.8kb2024-11-18 18:19:522024-11-18 18:19:56

Judging History

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

  • [2024-11-18 18:19:56]
  • 评测
  • 测评结果:WA
  • 用时:490ms
  • 内存:74648kb
  • [2024-11-18 18:19:52]
  • 提交

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;
            }
        }
    }
};

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;
            int k = j + n;
            if (i < n && k < m)
            {
                int x = lcp(i, k) + lcs(i, k) - 1;
                if (x >= d)
                {
                    std::cout << 2 * d << '\n';
                    return 0;
                }
                if (k + lcp(i, k) < m)
                {
                    int y = lcp(i + lcp(i, k) + n, k + lcp(i, k));
                    if (x + y >= d)
                    {
                        std::cout << 2 * d << '\n';
                        return 0;
                    }
                }
            }
            int x = lcp(i, j) + lcs(i, j) - 1;
            if (i > n && i - lcs(i, j) - n >= 0)
            {
                int y = lcs(i - lcs(i, j) - n, j - lcs(i, j));
                if (x + y >= d)
                {
                    std::cout << 2 * d << '\n';
                    return 0;
                }
            }
            else if (j < n && j + lcp(i, j) + n < m)
            {
                int 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 281ms
memory: 74428kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 251ms
memory: 74500kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

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

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 421ms
memory: 74488kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 206ms
memory: 74444kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 269ms
memory: 74500kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 490ms
memory: 74536kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: -3
Extra Test Failed : Wrong Answer on 4
time: 0ms
memory: 3580kb

input:

13
zcdefgbaijklm
zcdefghaabaaa

output:

2

result:

wrong answer 1st lines differ - expected: '8', found: '2'