QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714652#9522. A Simple String ProblemPixelCatAC ✓922ms173636kbC++175.1kb2024-11-06 01:41:312024-11-10 22:38:29

Judging History

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

  • [2024-11-10 22:38:29]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:922ms
  • 内存:173636kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:50:03]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1317ms
  • 内存:173560kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-11-06 01:41:31]
  • 评测
  • 测评结果:100
  • 用时:902ms
  • 内存:173632kb
  • [2024-11-06 01:41:31]
  • 提交

answer

#include <bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(0);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back

#define eb emplace_back

const int MAXN = 200'000;
const int LGN = 21;
const int N = MAXN * 2 + 10;

const int U = 1;
const int D = 2;

struct Bruh {
    int len, is_rev;
    int sa[N], tmp[2][N], c[N], rk[N], lcp[N], min_lcp[LGN][N];
    void buildSA(string s) {
        int *x = tmp[0], *y = tmp[1], m = 256, n = s.length();
        for(int i = 0; i < m; i++) c[i] = 0;
        for(int i = 0; i < n; i++) c[x[i] = s[i]]++;
        for(int i = 1; i < m; i++) c[i] += c[i - 1];
        for(int i = n - 1; ~i; --i) sa[--c[x[i]]] = i;
        for(int k = 1; k < n; k <<= 1) {
            for(int i = 0; i < m; i++) c[i] = 0;
            for(int i = 0; i < n; i++) c[x[i]]++;
            for(int i = 1; i < m; i++) c[i] += c[i - 1];
            int p = 0;
            for(int i = n - k; i < n; i++) y[p++] = i;
            for(int i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
            for(int i = n - 1; ~i; i--) sa[--c[x[y[i]]]] = y[i];
            y[sa[0]] = p = 0;
            for(int i = 1; i < n; i++) {
                int a = sa[i], b = sa[i - 1];
                if(!(x[a] == x[b] && a + k < n && b + k < n && x[a + k] == x[b + k])) p++;
                y[sa[i]] = p;
            }
            if(n == p + 1) break;
            swap(x, y), m = p + 1;
        }
    }
    void buildLCP(string s) {
        int n = s.length(), val = 0;
        for(int i = 0; i < n; i++) rk[sa[i]] = i;
        for(int i = 0; i < n; i++) {
            if(!rk[i]) lcp[rk[i]] = 0;
            else {
                if(val) val--;
                int p = sa[rk[i] - 1];
                while(val + i < n && val + p < n && s[val + i] == s[val + p]) val++;
                lcp[rk[i]] = val;
            }
        }
        for(int i = 1; i < n; i++) min_lcp[0][i] = lcp[i];
        for(int j = 0; j < LGN - 1; j++) {
            for(int i = 1; i < n; i++) {
                min_lcp[j + 1][i] = min_lcp[j][i];
                if(i + (1 << j) < n) min_lcp[j + 1][i] = min(min_lcp[j + 1][i], min_lcp[j][i + (1 << j)]);
            }
        }
    }
    void init(string &s, int _len, int _is_rev) {
        buildSA(s);
        buildLCP(s);
        len = _len;
        is_rev = _is_rev;
    }
    int mapid(int u, int i) {
        if(i < 0 || i >= len) return -1;
        if(is_rev) i = len - 1 - i;
        if(u == D) i += len + 1;
        return i;
    }
    int _match(int i, int j) {
        if(i < 0 || j < 0) return 0;
        assert(i != j);
        i = rk[i]; j = rk[j];
        if(i > j) swap(i, j);
        int k = __lg(j - i);
        return min(min_lcp[k][i + 1], min_lcp[k][j - (1 << k) + 1]);
    }
    int match(int u1, int i1, int u2, int i2) {
        return _match(mapid(u1, i1), mapid(u2, i2));
    }
} sa, as;

void findRep(int n, int l, int r, int &ans, int phase) {
    if(l == r) return;
    int m = (l + r - phase) / 2;
    findRep(n, l, m, ans, phase);
    findRep(n, m + 1, r, ans, phase);
    for(int i = l; i <= m; i++) {
        int k1, k2, k3;

        auto sanitize = [&](int matched, int len, int lineno) {
            if(len >= 8) {
                cout << l << " " << i << "-" << m << " " << r << ": " << k1 << " " << k2 << " " << k3 << " at line " << lineno << "\n";
            }
        };

        #ifndef NYA
        #define verify(len) {if((len) >= (m - i + 1)) ans = max(ans, (m - i + 1) * 2);}
        #else
        #define verify(len) {if((len) >= (m - i + 1)) {ans = max(ans, (m - i + 1) * 2); sanitize(len, (m - i + 1) * 2, __LINE__);}}
        #endif

        k1 = sa.match(D, i, D, m + 1);
        k2 = as.match(D, i - 1, D, m);
        k3 = as.match(U, i - 1 - k2, D, m - k2);
        verify(k1 + k2 + k3);

        k1 = sa.match(U, i, D, m + 1);
        k2 = as.match(U, i - 1, D, m);
        k3 = sa.match(D, i + k1, D, m + 1 + k1);
        verify(k1 + k2 + k3);

        k1 = sa.match(U, i, D, m + 1);
        k2 = as.match(U, i - 1, D, m);
        k3 = as.match(U, i - 1 - k2, U, m - k2);
        verify(k1 + k2 + k3);

        k1 = sa.match(U, i, U, m + 1);
        k2 = as.match(U, i - 1, U, m);
        k3 = sa.match(U, i + k1, D, m + 1 + k1);
        verify(k1 + k2 + k3);
    }
}

void solve()
{
    int n; cin >> n;
    string up, down; cin >> up >> down;
    up = up + "!";
    down = "?" + down;
    int ans = 0;
    rep(phase, 2) {
        string s;
        s = up + "$" + down;
        sa.init(s, n + 1, 0);
        // cout << s << "\n";
        reverse(up.begin(), up.end());
        reverse(down.begin(), down.end());
        s = up + "$" + down;
        as.init(s, n + 1, 1);
        // cout << s << "\n";
        findRep(n + 1, 0, n, ans, phase);
        swap(up, down);
    }
    cout << ans << "\n";
}

signed main()
{
    MottoHayaku
    int t;
    // cin>>t;
    t=1;
    while(t--)
    {
        solve();
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 922ms
memory: 173412kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 865ms
memory: 173416kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 858ms
memory: 173412kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 695ms
memory: 173340kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 705ms
memory: 173408kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 809ms
memory: 173548kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 549ms
memory: 173636kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 3ms
memory: 112104kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 4ms
memory: 112048kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed