Submission #707513

#	Time	Username	Problem	Language	Result	Execution time	Memory
707513		DennisTran	Palindromes (APIO14_palindrome)	C++17	73 / 100	1076 ms	89340 KiB

palindrome

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }

struct SUFFIX_ARRAY{
    vector<int> sort_cyclic_shifts(string const& s) {
        int n = s.size();
        const int alphabet = 256;
        vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
        for (int i = 0; i < n; i++) cnt[s[i]]++;
        for (int i = 1; i < alphabet; i++) cnt[i] += cnt[i - 1];
        for (int i = 0; i < n; i++) p[--cnt[s[i]]] = i;
        c[p[0]] = 0;
        int classes = 1;
        for (int i = 1; i < n; i++) {
            if (s[p[i]] != s[p[i-1]]) classes++;
            c[p[i]] = classes - 1;
        }
        vector<int> pn(n), cn(n);
        for (int h = 0; (1 << h) < n; ++h) {
            for (int i = 0; i < n; i++) {
                pn[i] = p[i] - (1 << h);
                if (pn[i] < 0) pn[i] += n;
            }
            fill(cnt.begin(), cnt.begin() + classes, 0);
            for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
            for (int i = 1; i < classes; i++) cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; i--) p[--cnt[c[pn[i]]]] = pn[i];
            cn[p[0]] = 0;
            classes = 1;
            for (int i = 1; i < n; i++) {
                pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
                pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
                if (cur != prev) ++classes;
                cn[p[i]] = classes - 1;
            }
            c.swap(cn);
        }
        return p;
    }

    vector<int> suffix_array(string s) {
        s += "$";
        vector<int> sorted_shifts = sort_cyclic_shifts(s);
        sorted_shifts.erase(sorted_shifts.begin());
        return sorted_shifts;
    }

    vector<int> kasai(string txt, vector<int> suffixArr) {
        int n = suffixArr.size();
        vector<int> lcp(n, 0);
        vector<int> invSuff(n, 0);
        for (int i = 0; i < n; i++) invSuff[suffixArr[i]] = i;
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (invSuff[i] == n - 1) {
                k = 0;
                continue;
            }
            int j = suffixArr[invSuff[i]+1];
            while (i + k < n && j + k < n && txt[i + k] == txt[j + k]) k++;
            lcp[invSuff[i]] = k;
            if (k > 0) k--;
        }
        return lcp;
    }
} T;

const int MAXN = 3e5 + 5;
const int MOD = 1e9 + 7;

int N, f[20][MAXN], pos[MAXN], Hash[2 * MAXN], Pow[2 * MAXN];
int suff[MAXN];

int get_lcp(int l, int r) {
    if (l == r) return N - l + 1;
    l = pos[l]; r = pos[r];
    if (l > r) swap(l, r); r--;
    int k = 31 - __builtin_clz(r - l + 1);
    return min(f[k][l], f[k][r - (1 << k) + 1]);
}

void Construct(string s) {
    N = s.size();
    vector <int> sa = T.suffix_array(s);
    vector <int> lcp = T.kasai(s, sa);


    REP(i, N) {
        pos[sa[i] + 1] = i + 1;
        f[0][i + 1] = lcp[i];
        suff[i + 1] = sa[i] + 1;
    }

    for (int i = 1; (1 << i) <= N; i++)
        for (int j = 1; j <= N - (1 << i) + 1; j++)
            f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
}

void Hashing(string s) {
    string t = s;
    reverse(ALL(t));
    s = ' ' + s + t;
    Pow[0] = 1;
    FOR(i, 1, 2 * N) {
        Hash[i] = (1ll * Hash[i - 1] * 31 + s[i] - 'a') % MOD;
        Pow[i] = 31ll * Pow[i - 1] % MOD;
    }
}

int code(int l, int r) {
    return (Hash[r] - 1ll * Hash[l - 1] * Pow[r - l + 1] % MOD + MOD) % MOD;
}

bool is_palindrome(int l, int r) {
    int u = l + r >> 1;
    int v = u + 1;
    if ((r - l + 1) & 1) v--;
    r = N - r + 1 + N;
    v = N - v + 1 + N;
    return code(l, u) == code(r, v);
}

unordered_set <int> dd[MAXN];
vector <pair <int, int>> Distinct_palindrome_substring(string s) {
    vector <pair <int, int>> ans;
    FOR(i, 1, N) {
        int l = 0, r = min(i, N - i + 1);
        while (r - l > 1) {
            int mid = l + r >> 1;
            if (is_palindrome(i - mid, i + mid)) l = mid;
            else r = mid;
        }
        int len = l;
        l = i - len, r = i + len;
        while (r >= l) {
            if (dd[r - l + 1].find(code(l, r)) != dd[r - l + 1].end()) break;
            dd[r - l + 1].insert(code(l, r));
            ans.emplace_back(l, r);
            l++; r--;
        }

        if (i < N && s[i] == s[i + 1]) {
            int l = 0, r = min(i, N - i);
            while (r - l > 1) {
                int mid = l + r >> 1;
                if (is_palindrome(i - mid, i + mid + 1)) l = mid;
                else r = mid;
            }
            len = l;
            l = i - len, r = i + 1 + len;
            while (r >= l) {
                if (dd[r - l + 1].find(code(l, r)) != dd[r - l + 1].end()) break;
                dd[r - l + 1].insert(code(l, r));
                ans.emplace_back(l, r);
                l++; r--;
            }
        }
    }
    return ans;
}

bool Lower_bound(int l, int r, int mid, string &s) {
    int len = get_lcp(l, mid);
    len = min(len, r - l + 1);
    if (len == r - l + 1) return true;
    if (len == N - mid + 1) return false;
    return s[l + len] < s[mid + len];
}

bool Upper_bound(int l, int r, int mid, string &s) {
    int len = get_lcp(l, mid);
    len = min(len, r - l + 1);
    if (len == r - l + 1) return false;
    if (len == N - mid + 1) return false;
    return s[l + len] < s[mid + len];
}

int count_occurences(int l, int r, string &s) {
    int L = 0, R = N + 1;
    while (R - L > 1) {
        int mid = L + R >> 1;
        if (Lower_bound(l, r, suff[mid], s)) R = mid;
        else L = mid;
    }
    int u = R, v = 0;
    L = 0, R = N + 1;
    while (R - L > 1) {
        int mid = L + R >> 1;
        if (Upper_bound(l, r, suff[mid], s)) R = mid;
        else L = mid;
    }
    v = R - 1;
    return v - u + 1;
}

signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //int T; cin >> T; while (T--)
    string s; cin >> s; 
    Construct(s);
    Hashing(s);

    s = ' ' + s;
    auto sets = Distinct_palindrome_substring(s);
    long long ans = 0;
    for (auto x : sets) {
        ans = max(ans, count_occurences(x.first, x.second, s) * (x.second - x.first + 1ll));
    }
    cout << ans;
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

palindrome.cpp: In function 'int get_lcp(int, int)':
palindrome.cpp:88:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   88 |     if (l > r) swap(l, r); r--;
      |     ^~
palindrome.cpp:88:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   88 |     if (l > r) swap(l, r); r--;
      |                            ^
palindrome.cpp: In function 'void Construct(std::string)':
palindrome.cpp:107:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  107 |             f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
      |                                                           ~~^~~
palindrome.cpp: In function 'bool is_palindrome(int, int)':
palindrome.cpp:126:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |     int u = l + r >> 1;
      |             ~~^~~
palindrome.cpp: In function 'std::vector<std::pair<int, int> > Distinct_palindrome_substring(std::string)':
palindrome.cpp:140:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  140 |             int mid = l + r >> 1;
      |                       ~~^~~
palindrome.cpp:156:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  156 |                 int mid = l + r >> 1;
      |                           ~~^~~
palindrome.cpp: In function 'int count_occurences(int, int, std::string&)':
palindrome.cpp:192:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  192 |         int mid = L + R >> 1;
      |                   ~~^~~
palindrome.cpp:199:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  199 |         int mid = L + R >> 1;
      |                   ~~^~~

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