Submission #1111679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111679		vjudge1	Palindromes (APIO14_palindrome)	C++17	100 / 100	33 ms	35032 KiB

palindrome

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 3e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

int to[MAXN][26], fail[MAXN], cnt[MAXN], len[MAXN], sz;

string s;

int extend() {
    fill(to[sz], to[sz] + 26, 0), sz++;
    return sz - 1;
}
void init() {
    sz = 0, extend(), extend();
    len[0] = 0, fail[0] = 1, len[1] = -1;
    int last = 1;
    rep (i, 0, s.size()) {
        while (s[i - len[last] - 1] != s[i]) last = fail[last];
        if (!to[last][s[i] - 'a']) {
            int idx = extend();
            len[idx] = len[last] + 2;
            int now = fail[last];
            while (s[i - len[now] - 1] != s[i]) now = fail[now];
            fail[idx] = to[now][s[i] - 'a'];
            to[last][s[i] - 'a'] = idx;
        }
        last = to[last][s[i] - 'a'];
        cnt[last]++;
    }
}
void build_count() {
    for (int i = sz - 1; i > 1; --i) cnt[fail[i]] += cnt[i];
}

void solve() {
    cin >> s;
    init();
    build_count();
    ll ans = 0;
    rep (i, 0, sz) chmax(ans, 1LL * len[i] * cnt[i]);
    cout << ans << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

Compilation message (stderr)

palindrome.cpp: In function 'void init()':
palindrome.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define rep(X, a, b) for(int X = a; X < b; ++X)
......
   55 |     rep (i, 0, s.size()) {
      |          ~~~~~~~~~~~~~~                
palindrome.cpp:55:5: note: in expansion of macro 'rep'
   55 |     rep (i, 0, s.size()) {
      |     ^~~

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