제출 #677880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677880		Romiros	Palindromes (APIO14_palindrome)	C++17	73 / 100	1076 ms	73412 KiB

palindrome

#include <bits/stdc++.h>
 
#define ll long long
#define ld long double
#define vi vector<int>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ull H
 
using namespace std;
 
const int MAXN = 3e5 + 10;
 
const int MOD[2] = {(int)(1e9 + 7), (int)(1e9 + 9)};
 
struct H{
    ll h[2];
 
    H(int x = 0, int y = 0){
        h[0] = x;
        h[1] = y;
    }
};
 
H operator+(const H& a, const H& b){
    H c = a;
    for (int i = 0; i < 2; i++){
        c.h[i] = (a.h[i] + b.h[i]) % MOD[i];
    }
    return c;
}
 
H operator-(const H& a, const H& b){
    H c = a;
    for (int i = 0; i < 2; i++){
        c.h[i] = (a.h[i] - b.h[i] + MOD[i]) % MOD[i];
    }
    return c;
}
 
H operator*(const H& a, const H& b){
    H c = a;
    for (int i = 0; i < 2; i++){
        c.h[i] = (a.h[i] * 1ll * b.h[i]) % MOD[i];
    }
    return c;
}
 
bool operator==(const H& a, const H& b){
    for (int i = 0; i < 2; i++){
        if (a.h[i] != b.h[i]){
            return 0;
        }
    }
    return 1;
}

ull pw[MAXN + 10];
ull pref[MAXN];
ull suff[MAXN];
int n;
 
ull h(int i, int j){
    return (pref[j] - pref[i - 1]) * pw[MAXN - i + 1];
}
 
ull rh(int i, int j){
    return (suff[i] - suff[j + 1]) * pw[MAXN + j - n];
}
 
vector<int> build_sa(string s){
    int n = s.size();
    vector<int> a(n);
    vector<int> eq(2 * n + 1);
    vector<int> nw(2 * n + 1);
    vector<int> t(n + 1);
    vector<int> nw_a(n);
    for (int i = 0; i < n; i++){
        a[i] = i;
    }
    sort(a.begin(), a.end(), [&](int x, int y){
        return s[x] < s[y] || (s[x] == s[y] && x < y);
    });
    eq[a[0]] = 1;
    for (int i = 1; i < n; i++){
        eq[a[i]] = eq[a[i - 1]] + (s[a[i]] != s[a[i - 1]]);
    }
    for (int k = 0; (1 << k) <= n; k++){
        for (int f = 1; f >= 0; f--){
            t.assign(n + 1, 0);
            for (int i = 0; i < n; i++){
                int j = a[i] + (f << k);
                t[eq[j]]++;
            }
            for (int i = 1; i <= n; i++){
                t[i] += t[i - 1];
            }
            for (int i = n; i >= 1; i--){
                t[i] = t[i - 1];
            }
            t[0] = 0;
            for (int i = 0; i < n; i++){
                int j = a[i] + (f << k);
                nw_a[t[eq[j]]++] = a[i];
            }
            nw_a.swap(a);
        }
        nw[a[0]] = 1;
        for (int i = 1; i < n; i++){
            int p = a[i];
            int q = a[i - 1];
            nw[p] = nw[q];
            if (eq[p] != eq[q] || eq[p + (1 << k)] != eq[q + (1 << k)]){
                nw[p]++;
            }
        }
        nw.swap(eq);
    }
    a.insert(a.begin(), n);
    return a;
}
 
vector<int> build_lcp(const vector<int>& p, const string& s){
    int n = s.size();
    vector<int> pos(n + 1);
    for (int i = 0; i <= n; i++){
        pos[p[i]] = i;
    }
    vector<int> lcp(n);
    int k = 0;
    for (int i = 0; i < (n - 1); i++){
        while (s[i + k] == s[p[pos[i] - 1] + k]){
            k++;
        }
        lcp[pos[i] - 1] = k;
        k -= (k != 0);
    }
    return lcp;
}

struct SparseTable{
    vector<vector<int>> st;

    SparseTable(vector<int> a){
        int n = a.size();
        st.resize(n);
        for (int i = 0; i < n; i++){
            st[i].push_back(a[i]);
        }
        for (int k = 1; k <= n; k *= 2){
            for (int i = 0; i + k < n; i++){
                st[i].push_back(min(st[i].back(), st[i + k].back()));
            }
        }
    }

    int log2(int x){
        return 31 - __builtin_clz(x);
    }

    int get(int l, int r){
        if (l > r){
            return 1e9;
        }
        int k = log2(r - l + 1);
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef ON_PC
        freopen("input.txt", "r", stdin);
    #endif
    // freopen("output.txt", "w", stdout);
    pw[0] = {1, 1};
    for (int i = 1; i < MAXN + 10; i++){
        pw[i] = pw[i - 1] * H{57, 113};
    }
    int T = 1;
    // cin >> T;
    while (T--){
        string s;
        cin >> s;
        n = s.size();   
        vector<int> sa = build_sa(s);
        vector<int> lcpv = build_lcp(sa, s);
        vector<int> pos(n + 2);
        for (int i = 0; i < sa.size(); i++){
            pos[sa[i] + 1] = i;
        }
        SparseTable sp(lcpv);
        s = " " + s;
        for (int i = 1; i <= n; i++){
            pref[i] = pref[i - 1] + (s[i] - 'a' + 1) * pw[i - 1];
        }
        for (int i = n; i >= 1; i--){
            suff[i] = suff[i + 1] + (s[i] - 'a' + 1) * pw[n - i];
        }
        ll res = 0;
        for (int f = 0; f < 2; f++){
            vector<int> d(n + 1);
            for (int i = 1, l = 0, r = -1; i <= n; i++){
                if (i + f <= r){
                    d[i] = min(r - (i + f) + 1, d[l + r - (i + f)]);
                }
                while (i - d[i] >= 1 && i + f + d[i] <= n && 
                       s[i - d[i]] == s[i + f + d[i]]){
                           d[i]++;
                }
                if (i + f + d[i] - 1 > r){
                    r = i + f + d[i] - 1;
                    l = i - d[i] + 1;
                }
            }
            for (int i = 1; i <= n; i++){
                res = max(res, (ll)(2 * d[i] - !f));
            }
            vector<int> order(n);
            for (int i = 1; i <= n; i++){
                order[i - 1] = i;
            }
            function<int(int, int)> lcp = [&](int i, int j){
                int l = pos[i];
                int r = pos[j];
                if (l > r){
                    swap(l, r);
                }
                return min({d[i], d[j], sp.get(l, r - 1)});
                // int l = 0, r = min(d[i], d[j]) + 1;
                // while (r - l > 1){
                //     int m = (l + r) / 2;
                //     if (h(i - m + 1, i) == h(j - m + 1, j)){
                //         l = m;
                //     } else {
                //         r = m;
                //     }
                // }
                // return l;
            };
            sort(all(order), [&](int i, int j){
                int l = lcp(i, j);
                if (l == min(d[i], d[j])){
                    if (d[i] != d[j]){
                        return d[i] < d[j];
                    }
                    return i < j;
                }
                return s[i - l] < s[j - l];
            });
            vector<int> lcp_res(n);
            for (int i = 0; i + 1 < n; i++){
                lcp_res[i] = lcp(order[i], order[i + 1]);
            }
            vector<int> lb(n);
            vector<int> rb(n);
            vector<int> st;
            for (int i = 0; i < n; i++){
                while (!st.empty() && lcp_res[st.back()] >= lcp_res[i]){
                    st.pop_back();
                }
                lb[i] = 0;
                if (!st.empty()){
                    lb[i] = st.back() + 1;
                }
                st.push_back(i);
            }
            st.clear();
            for (int i = n - 1; i >= 0; i--){
                while (!st.empty() && lcp_res[st.back()] >= lcp_res[i]){
                    st.pop_back();
                }
                rb[i] = n - 1;
                if (!st.empty()){
                    rb[i] = st.back();
                }
                st.push_back(i);
            }
            st.clear();
            for (int i = 0; i < n; i++){
                res = max(res, (2 * lcp_res[i] - !f) * 1ll * (rb[i] - lb[i] + 1));
                // int mn = d[order[i]];
                // for (int j = i; j < n; j++){
                //     res = max(res, (j - i + 1) * 1ll * (2 * mn - !f));
                //     if (j + 1 < n){
                //         mn = min(mn, lcp_res[j]);
                //     }
                // }
            }
        }
        cout << res << "\n";
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int main()':
palindrome.cpp:192:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |         for (int i = 0; i < sa.size(); i++){
      |                         ~~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 0 / 27