QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#680102#9522. A Simple String Problemucup-team296#AC ✓1002ms79288kbC++205.5kb2024-10-26 19:49:592024-11-10 22:36:53

Judging History

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

  • [2024-11-10 22:36:53]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1002ms
  • 内存:79288kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:48:26]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:947ms
  • 内存:79252kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-28 15:18:08]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1296ms
  • 内存:79128kb
  • [2024-10-28 15:17:17]
  • hack成功,自动添加数据
  • (/hack/1080)
  • [2024-10-28 14:30:10]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1093ms
  • 内存:79252kb
  • [2024-10-28 14:28:57]
  • hack成功,自动添加数据
  • (/hack/1079)
  • [2024-10-27 18:37:53]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1382ms
  • 内存:79176kb
  • [2024-10-27 18:36:42]
  • hack成功,自动添加数据
  • (/hack/1075)
  • [2024-10-26 19:50:19]
  • 评测
  • 测评结果:100
  • 用时:999ms
  • 内存:79100kb
  • [2024-10-26 19:49:59]
  • 提交

answer

#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

struct sufmas {

    void count_sort(vector<int> &p, vector<int> &c) {
        int n = p.size();
        vector<int> cnt(n);
        for (auto x: c) {
            cnt[x]++;
        }
        vector<int> p_new(n);
        vector<int> pos(n);
        pos[0] = 0;
        for (int i = 1; i < n; i++) {
            pos[i] = pos[i - 1] + cnt[i - 1];
        }
        for (auto x: p) {
            int i = c[x];
            p_new[pos[i]] = x;
            pos[i]++;
        }
        p = p_new;
    }

    vector<int> p;
    vector<int> c;
    vector<int> lcp;
    vector<vector<int>> st;
    const int MAX = 20;
    const char SPECIAL = 0;

    string ss;

    sufmas(string s) {
//        ss = s;

//        cout << s << "\n";
        s += SPECIAL;
        int n = s.size();
        p.resize(n);
        c.resize(n);
        {
            // k = 0
            vector<pair<char, int>> a(n);
            for (int i = 0; i < n; i++) a[i] = {s[i], i};
            sort(a.begin(), a.end());

            for (int i = 0; i < n; i++) p[i] = a[i].second;
            c[p[0]] = 0;
            for (int i = 1; i < n; i++) {
                if (a[i].first == a[i - 1].first && a[i].first != SPECIAL) {
                    c[p[i]] = c[p[i - 1]];
                } else {
                    c[p[i]] = c[p[i - 1]] + 1;
                }
            }
        }

        int k = 0;
        while ((1 << k) < n) {
            // k -> k + 1

            for (int i = 0; i < n; i++) {
                p[i] = (p[i] - (1 << k) + n) % n;
            }

            count_sort(p, c);

            vector<int> c_new(n);
            c_new[p[0]] = 0;
            for (int i = 1; i < n; i++) {
                pair<int, int> prev = {c[p[i - 1]], c[(p[i - 1] + (1 << k)) % n]};
                pair<int, int> now = {c[p[i]], c[(p[i] + (1 << k)) % n]};
                if (now == prev) {
                    c_new[p[i]] = c_new[p[i - 1]];
                } else {
                    c_new[p[i]] = c_new[p[i - 1]] + 1;
                }
            }
            c = c_new;
            k++;
        }

        lcp.resize(n);
        k = 0;
        for (int i = 0; i < n - 1; i++) {
            int pi = c[i];
            if (pi > 0) {
                int j = p[pi - 1];
                // lcp[i] = lcp(s[i..], s[j..])
                while (s[i + k] == s[j + k] && s[i + k] != SPECIAL) k++;
            }
            lcp[pi] = k;
            k = max(k - 1, 0);
        }

        st.assign(MAX, vector<int>(n));
        st[0] = lcp;
        for (int k = 1; k < MAX; k++) {
            for (int i = 0; i + (1 << k) <= n; i++) {
                st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    int get_lcp(int i, int j) {
        if (i == p.size() || j == p.size()) return 0;
        i = c[i];
        j = c[j];
        if (i > j) swap(i, j);
        i++,j++;
        int d = (j - i);
        int k = 0;
        while ((1 << (k + 1)) <= d) k++;
        return min(st[k][i], st[k][j - (1 << k)]);
    }

};

int n;

int lcp(int c1, int p1, int c2, int p2, sufmas &sm1) {
    return sm1.get_lcp(c1 * n + p1, c2 * n + p2);
}

int rlcp(int c1, int p1, int c2, int p2, sufmas &sm2) {
    return sm2.get_lcp(2 * n - 1 - c1 * n - p1, 2 * n - 1 - c2 * n - p2);
}

int res = 0;

void go(int l, int r, sufmas &sm1, sufmas &sm2) {
    if (r - l < 2) return;
    int m = (l + r) / 2;
    go(l, m, sm1, sm2);
    go(m, r, sm1, sm2);
    for (int i = m + 1; i <= r; i++) {
        int len = i - m;
        if (len <= res) continue;
        {
            int x = rlcp(0, m - 1, 0, i - 1, sm2);
            x = min(x, len);
            x = min(x, m - l);
            int y = lcp(0, m, 0, i, sm1);
            y = min(y, len);
            y = min(y, r - i);
            int z = 0;
            if (x + y < len) {
                z = lcp(0, m + y, 1, i + y, sm1);
            }
            if (x + y + z >= len) {
                res = max(res, len);
            }
        }
        {
            int x = rlcp(0, m - 1, 1, i - 1, sm2);
            x = min(x, len);
            x = min(x, m - l);
            int y = lcp(0, m, 1, i, sm1);
            y = min(y, len);
            y = min(y, r - i);
            int z = 0;
            if (x + y < len) {
                z = max(
                        lcp(1, m + y, 1, i + y, sm1),
                        rlcp(0, m - 1 - x, 0, i - 1 - x, sm2));
            }
            if (x + y + z >= len) {
                res = max(res, len);
            }
        }
    }
    for (int i = l; i < m; i++) {
        int len = m - i;
        if (len <= res) continue;
        {
            int x = rlcp(0, i - 1, 0, m - 1, sm2);
            x = min(x, len);
            x = min(x, m - l);
            int y = lcp(0, i, 0, m, sm1);
            int z = 0;
            if (x + y < len) {
                z = lcp(0, i + y, 1, m + y, sm1);
            }
            if (x + y + z >= len) {
                res = max(res, len);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);

    string s1, s2;

    cin >> n >> s1 >> s2;

    s1 = s1 + '$';
    s2 = '$' + s2;
    n++;

    string r = s1 + s2;
    sufmas sm1(r);
    reverse(r.begin(), r.end());
    sufmas sm2(r);

    go(0, n, sm1, sm2);
    go(0, n, sm2, sm1);

    cout << res * 2 << "\n";

    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

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: 3568kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 1002ms
memory: 78996kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 699ms
memory: 79232kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 971ms
memory: 78928kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 766ms
memory: 78996kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 267ms
memory: 79288kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 513ms
memory: 78956kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 974ms
memory: 79168kb

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: 3572kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed