QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760819#9522. A Simple String ProblemClarusWA 639ms74548kbC++204.8kb2024-11-18 19:24:312024-11-18 19:24:31

Judging History

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

  • [2024-11-18 19:24:31]
  • 评测
  • 测评结果:WA
  • 用时:639ms
  • 内存:74548kb
  • [2024-11-18 19:24:31]
  • 提交

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];
        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 k = i + d + 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;
                    }
                }
            }
        }
        if (d == 1) { continue; }
        for (int i = 0; i + d < m; i += d - 1)
        {
            int j = i + d;
            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: 3512kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 274ms
memory: 74316kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

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

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 270ms
memory: 74548kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

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

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 227ms
memory: 74540kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 233ms
memory: 74440kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 550ms
memory: 74392kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: -3
Extra Test Failed : Wrong Answer on 5
time: 506ms
memory: 74612kb

input:

200000
babbbaababbabbbbbbabbaaaaaabaababaabababbbabbaaaaaaabbababaaababaaabaabaabbabbbabbbaabbbaaaaaaaaababbaaaabaaababbabababaaabaaabbabbbaaabbaabbabbabaabbbbbababaaaabbbbbabaaaabaabababbabbabbabbbabbaabaaaabbaabbbbbaaaabbaababaaaaabaaabbbababaababaaababbaaaaaabbababaababbbbbbaaabbaababbaaaaabbbaba...

output:

42

result:

wrong answer 1st lines differ - expected: '50', found: '42'