QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#734080#9522. A Simple String ProblembecaidoAC ✓651ms75288kbC++205.7kb2024-11-10 23:46:242024-11-10 23:46:24

Judging History

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

  • [2024-11-10 23:46:24]
  • 评测
  • 测评结果:AC
  • 用时:651ms
  • 内存:75288kb
  • [2024-11-10 23:46:24]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

vector<int> suffix_array(string s) {
    int n = s.size();
    if (n == 1) return {0};
    s += "\0";
    vector<int> sa(n + 1), rnk(n + 1), cnt(n + 1);
    array<int, 256> alp{};
    for (int i = 0; i <= n; i++) alp[s[i]]++;
    for (int i = 1; i < 256; i++) alp[i] += alp[i - 1];
    for (int i = 0; i <= n; i++) sa[--alp[s[i]]] = i;
    for (int i = 1, cur = 0; i <= n; i++) {
        if (s[sa[i]] != s[sa[i - 1]]) cur++;
        rnk[sa[i]] = cur;
    }
    for (int len = 1; len <= n; len <<= 1) {
        vector<int> lp(n + 1), nrnk(n + 1);
        fill(cnt.begin(), cnt.end(), 0);
        for (int i = 0; i <= n; i++) {
            lp[i] = sa[i] - len;
            if (lp[i] < 0) lp[i] += n + 1;
            cnt[rnk[i]]++;
        }
        for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 0; i--) sa[--cnt[rnk[lp[i]]]] = lp[i];
        nrnk[sa[0]] = 0;
        for (int i = 1, cur = 0; i <= n; i++) {
            int np1 = sa[i] + len, np2 = sa[i - 1] + len;
            if (np1 > n + 1) np1 -= n + 1;
            if (np2 > n + 1) np2 -= n + 1;
            if (rnk[sa[i]] != rnk[sa[i - 1]] || rnk[np1] != rnk[np2]) cur++;
            nrnk[sa[i]] = cur;
        }
        rnk = nrnk;
    }
    sa.erase(sa.begin());
    return sa;
}
vector<int> lcp_array(string s, vector<int> sa = {}) {
    int n = s.size(), len = 0;
    if (sa.size() == 0) sa = suffix_array(s);
    vector<int> rnk(n), lcp(n - 1);
    for (int i = 0; i < n; i++) rnk[sa[i]] = i;
    for (int i = 0; i < n; i++) {
        if (rnk[i] == n - 1) {
            len = 0;
            continue;
        }
        int j = sa[rnk[i] + 1];
        while (i + len < n && j + len < n && s[i + len] == s[j + len]) len++;
        lcp[rnk[i]] = len;
        len = max(0, len - 1);
    }
    return lcp;
}

const int SIZE = 4e5 + 500;
const int H = __lg(SIZE);

int n;
string a, b, s1, s2;
vector<int> sa1, sa2, rnk1, rnk2, lcp1, lcp2;

struct ST {
    int mn[SIZE][H + 1];
    void build(vector<int> v) {
        int n = v.size();
        FOR (i, 0, n - 1) mn[i][0] = v[i];
        for (int j = 1, len = 2; len <= n; j++, len <<= 1) {
            FOR (i, 0, n - len) {
                mn[i][j] = min(mn[i][j - 1], mn[i + (len >> 1)][j - 1]);
            }
        }
    }
    int que(int l, int r) {
        if (l == r) return n;
        r--;
        int h = __lg(r - l + 1);
        return min(mn[l][h], mn[r - (1 << h) + 1][h]);
    }
} st1, st2;

int lcp(int t1, int l1, int r1, int t2, int l2, int r2) {
    if (l1 > r1 || l2 > r2) return 0;
    int x = (t1 == 0 ? rnk1[l1] : rnk1[n + l1]);
    int y = (t2 == 0 ? rnk1[l2] : rnk1[n + l2]);
    if (x > y) swap(x, y);
    int re = st1.que(x, y);
    re = min({re, r1 - l1 + 1, r2 - l2 + 1});
    return re;
}
int lcs(int t1, int l1, int r1, int t2, int l2, int r2) {
    if (l1 > r1 || l2 > r2) return 0;
    int x = (t1 == 0 ? rnk2[2 * n - r1 - 1] : rnk2[n - r1 - 1]);
    int y = (t2 == 0 ? rnk2[2 * n - r2 - 1] : rnk2[n - r2 - 1]);
    if (x > y) swap(x, y);
    int re = st2.que(x, y);
    re = min({re, r1 - l1 + 1, r2 - l2 + 1});
    return re;
}

void solve() {
    cin >> n >> a >> b;
    n++, a += "$", b = "$" + b;
    s1 = s2 = a + b;
    reverse(s2.begin(), s2.end());
    sa1 = suffix_array(s1), lcp1 = lcp_array(s1, sa1);
    sa2 = suffix_array(s2), lcp2 = lcp_array(s2, sa2);
    st1.build(lcp1), st2.build(lcp2);
    rnk1.resize(sa1.size()), rnk2.resize(sa2.size());
    FOR (i, 0, sa1.size() - 1) {
        rnk1[sa1[i]] = i;
        rnk2[sa2[i]] = i;
    }

    for (int len = (n + 1) / 2; len >= 1; len--) {
        for (int l = 0, r = len - 1; r < n; l += len, r += len) {
            {
                int R = r + lcp(1, l, n - 1, 1, r + 1, n - 1);
                int L = l - lcs(1, 0, r, 1, 0, l - 1);
                int aL = L - lcs(1, L, L + len - 1, 0, 0, L - 1);
                if (R - aL + 1 >= 2 * len) {
                    cout << 2 * len << '\n';
                    return;
                }
            }
            {
                int L = l - lcs(0, 0, r, 0, 0, l - 1);
                int R = r + lcp(0, l, n - 1, 0, r + 1, n - 1);
                int bR = R + lcp(0, R - len + 1, R, 1, R + 1, n - 1);
                if (bR - L + 1 >= 2 * len) {
                    cout << 2 * len << '\n';
                    return;
                }
            }
            {
                int len1 = lcs(0, 0, l - 1, 1, l, r);
                int len2 = lcp(1, r + 1, n - 1, 0, l, r);
                if (len1 + len2 >= len) {
                    cout << 2 * len << '\n';
                    return;
                }
                int len3 = len2 + lcp(1, r + 1 + len2, n - 1, 1, l + len2, r);
                if (len1 + len3 >= len) {
                    cout << 2 * len << '\n';
                    return;
                }
                len3 = len1 + lcs(0, 0, l - 1 - len1, 0, l, r - len1);
                if (len2 + len3 >= len) {
                    cout << 2 * len << '\n';
                    return;
                }
            }
        }
    }
    cout << "0\n";
}

int main() {
    Waimai;
    solve();
}

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

详细

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 291ms
memory: 75228kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 276ms
memory: 74044kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 278ms
memory: 75240kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 562ms
memory: 75288kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 200ms
memory: 75064kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 195ms
memory: 75128kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 651ms
memory: 75224kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed