QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#683948#9522. A Simple String Problemucup-team3215AC ✓832ms79992kbC++233.9kb2024-10-28 04:07:222024-10-28 04:07:23

Judging History

你现在查看的是测评时间为 2024-10-28 04:07:23 的历史记录

  • [2024-11-10 22:37:12]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:912ms
  • 内存:81740kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:48:44]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:940ms
  • 内存:80516kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-28 15:18:53]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:956ms
  • 内存:80520kb
  • [2024-10-28 15:17:17]
  • hack成功,自动添加数据
  • (/hack/1080)
  • [2024-10-28 14:31:09]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:886ms
  • 内存:80260kb
  • [2024-10-28 14:28:57]
  • hack成功,自动添加数据
  • (/hack/1079)
  • [2024-10-28 04:07:23]
  • 评测
  • 测评结果:100
  • 用时:832ms
  • 内存:79992kb
  • [2024-10-28 04:07:22]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
#define sz(c) (int)c.size()
#define all(c) c.begin(),c.end()
#define rep(i, l, r) for(int i =l;i < r;++i)

struct SuffixArray {
    vi sa, lcp;

    SuffixArray(string &s, int lim = 256) { // or basic_string<int>
        int n = sz(s) + 1, k = 0, a, b;
        vi x(all(s)), y(n), ws(max(n, lim));
        x.push_back(0), sa = lcp = y, iota(all(sa), 0);
        for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
            p = j, iota(all(y), n - j);
            rep(i, 0, n) if (sa[i] >= j) y[p++] = sa[i] - j;
            fill(all(ws), 0);
            rep(i, 0, n) ws[x[i]]++;
            rep(i, 1, lim) ws[i] += ws[i - 1];
            for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
            swap(x, y), p = 1, x[sa[0]] = 0;
            rep(i, 1, n) a = sa[i - 1], b = sa[i], x[b] =
                        (y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
        }
        for (int i = 0, j; i < n - 1; lcp[x[i++]] = k)
            for (k &&k--, j = sa[x[i] - 1];
                    s[i + k] == s[j + k];
        k++);
    }
};

constexpr int LOG = 20;

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    int res = 0;
    auto solve = [&] {
        string q = s;
        q += 'z' + 1;
        q += t;
        q += 'z' + 2;
        q += string(s.rbegin(), s.rend());
        q += 'z' + 3;
        q += string(t.rbegin(), t.rend());
        auto SA = SuffixArray(q);
        vector<vector<int>> sp(LOG);
        int N = SA.sa.size();
        sp[0] = SA.lcp;
        for (int i = 1; i < LOG; ++i) {
            sp[i].resize(N);
            for (int j = 0; j + (1 << i) - 1 < sp[i].size(); ++j) {
                sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
            }
        }
        vector<int> pos(N);
        for (int i = 0; i < N; ++i) {
            pos[SA.sa[i]] = i;
        }
        auto ask = [&](int l, int r) {
            if (l >= r)return 0;
            int len = r - l;
            int lg = __lg(len);
            return min(sp[lg][l], sp[lg][r - (1 << lg)]);
        };
        auto lcp = [&](int x, int y) {
            x = pos[x], y = pos[y];
            if (x > y)swap(x, y);
            if (x < 0 || y > N)return 0;
            return ask(x + 1, y + 1);
        };
        auto rev = [&](int i) {
            return n - i - 1;
        };
        for (int l = 1; l <= n; ++l) {
            for (int i = 0; i + l - 1 < n; i += l) {
                // stupid
                {
                    int lq = i, rq = i + l - 1;
                    rq += lcp(i, i + l);
                    lq -= lcp(rev(i + l - 1) + 2 * (n + 1), rev(i - 1) + 2 * (n + 1));
                    if (rq - lq + 1 >= 2 * l) {
                        res = max(res, l);
                        continue;
                    }
                    rq += lcp(i + (rq + 1) % l, rq + 1 + (n + 1) - 1);
                    if (rq - lq + 1 >= 2 * l) {
                        res = max(res, l);
                    }
                }
                {
                    int pf = lcp(i, i + l + (n + 1) - 1);
                    int sf = lcp(rev(i - 1) + 2 * (n + 1), rev(i + l - 1 - 1) + 3 * (n + 1));
                    if (pf + sf >= l) {
                        res = max(res, l);
                        continue;
                    }
                    int need = l - pf - sf;
                    if (lcp(rev(i + l - 1 - sf) + 2 * (n + 1), rev(i - 1 - sf) + 2 * (n + 1)) >= need)res = max(res, l);
                    if (lcp(i + pf + (n + 1) - 1, i + l + pf + (n + 1) - 1) >= need)res = max(res, l);
                }
            }
        }
    };
    solve();
    swap(s, t);
    reverse(s.begin(), s.end());
    reverse(t.begin(), t.end());
    solve();
    cout << res * 2;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 832ms
memory: 79320kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 802ms
memory: 79468kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 816ms
memory: 78728kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 669ms
memory: 79992kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 611ms
memory: 79096kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 748ms
memory: 78592kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 515ms
memory: 79844kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

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

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed