Submission #969000

#	Time	Username	Problem	Language	Result	Execution time	Memory
969000		Nhoksocqt1	Palindromes (APIO14_palindrome)	C++17	100 / 100	491 ms	91312 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const bool isMultiTest = 0;
const int MAXN = 300005;
const int NMOD = 2;

const int MOD[] = {int(1e9) + 2277, int(1e9) + 5277, int(1e9) + 8277};
const int BASE = 256;

ll pw[NMOD][MAXN];

struct Hash {
    ll value[NMOD];

    Hash(char c = 0) {
        for (int i = 0; i < NMOD; ++i)
            value[i] = c;
    }

    Hash operator + (const Hash &h) const {
        Hash res;
        for (int i = 0; i < NMOD; ++i) {
            res.value[i] = value[i] + h.value[i];
            if(res.value[i] >= MOD[i])
                res.value[i] -= MOD[i];
        }

        return res;
    }

    Hash operator - (const Hash &h) const {
        Hash res;
        for (int i = 0; i < NMOD; ++i) {
            res.value[i] = value[i] - h.value[i];
            if(res.value[i] < 0)
                res.value[i] += MOD[i];
        }

        return res;
    }

    Hash operator * (int k) const {
        Hash res;
        for (int i = 0; i < NMOD; ++i)
            res.value[i] = value[i] * pw[i][k] % MOD[i];

        return res;
    }

    bool operator == (const Hash &h) const {
        for (int i = 0; i < NMOD; ++i) {
            if(value[i] != h.value[i])
                return false;
        }

        return true;
    }
} hashVal[MAXN], revHashVal[MAXN];

string str;
int Plcp[MAXN][19], cnt[MAXN], tmp[MAXN];
int P[2][MAXN][19], maxPalin[2][MAXN];
int sa[MAXN], pos[MAXN], lcp[MAXN], strLen;

int gap;
bool sufCmp(int i, int j) {
    if(pos[i] != pos[j])
        return (pos[i] < pos[j]);

    return (max(i, j) + gap > strLen) ? (i > j) : (pos[i + gap] < pos[j + gap]);
}

void countsort(int gap) {
    for (int i = 1; i <= max(256, strLen); ++i)
        cnt[i] = 0;

    for (int i = 1; i <= strLen; ++i)
        ++cnt[(i + gap <= strLen ? pos[i + gap] : 0)];

    for (int i = 1; i <= max(256, strLen); ++i)
        cnt[i] += cnt[i - 1];

    for (int i = strLen; i > 0; --i)
        tmp[cnt[(sa[i] + gap <= strLen ? pos[sa[i] + gap] : 0)]--] = sa[i];

    for (int i = 1; i <= strLen; ++i)
        sa[i] = tmp[i];
}

void buildSA(void) {
    for (int i = 1; i <= strLen; ++i)
        sa[i] = i, pos[i] = str[i];

    for (gap = 1; gap <= strLen; gap <<= 1) {
        countsort(gap);
        countsort(0);

        tmp[sa[1]] = 1;
        for (int i = 2; i <= strLen; ++i)
            tmp[sa[i]] = tmp[sa[i - 1]] + sufCmp(sa[i - 1], sa[i]);

        for (int i = 1; i <= strLen; ++i)
            pos[i] = tmp[i];

        if(tmp[sa[strLen]] == strLen)
            break;
    }
}

void buildLCP(void) {
    int k(0);
    for (int i = 1; i <= strLen; ++i) {
        if(pos[i] != strLen) {
            for (int j = sa[pos[i] + 1]; str[i + k] == str[j + k]; ) ++k;
            lcp[pos[i]] = k;
            k -= (k > 0);
        }
    }
}

inline int getLCP(int l, int r) {
    int log = 31 - __builtin_clz(r - l + 1);
    return min(Plcp[l][log], Plcp[r - (1 << log) + 1][log]);
}

void init(void) {
    for (int i = 0; i < NMOD; ++i) {
        pw[i][0] = 1;
        for (int j = 1; j < MAXN; ++j)
            pw[i][j] = pw[i][j - 1] * BASE % MOD[i];
    }
}

inline Hash getHash(int l, int r) {
    return (hashVal[r] - hashVal[l - 1]) * (strLen - r);
}

inline Hash getRevHash(int l, int r) {
    return (revHashVal[l] - revHashVal[r + 1]) * (l - 1);
}

inline int getMax(int P[][19], int l, int r) {
    int log = 31 - __builtin_clz(r - l + 1);
    return max(P[l][log], P[r - (1 << log) + 1][log]);
}

void process(void) {
    cin >> str;
    strLen = sz(str);
    str = '^' + str;

    buildSA();
    buildLCP();

    init();
    for (int i = 1; i <= strLen; ++i)
        hashVal[i] = hashVal[i - 1] + Hash(str[i]) * i;

    for (int i = strLen; i > 0; --i)
        revHashVal[i] = revHashVal[i + 1] + Hash(str[i]) * (strLen - i + 1);

    for (int i = 1; i <= strLen; ++i) {
        int l(1), r = min(i, strLen - i + 1), opt(0);
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(getHash(i - mid + 1, i) == getRevHash(i, i + mid - 1)) {
                opt = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        maxPalin[0][i] = 2 * opt - 1;
        if(i == strLen || str[i] != str[i + 1])
            continue;

        l = 1, r = min(i, strLen - i), opt = 0;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(getHash(i - mid + 1, i) == getRevHash(i + 1, i + mid)) {
                opt = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        maxPalin[1][i] = 2 * opt;
    }

    ll res(0);
    for (int i = strLen; i > 0; --i) {
        res = max(res, ll(max(maxPalin[0][i], maxPalin[1][i])));
        P[0][i][0] = maxPalin[0][i] - 2 * i;
        P[1][i][0] = maxPalin[1][i] - 2 * i;
        Plcp[i][0] = lcp[i];
    }

    for (int j = 1; (1 << j) <= strLen; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= strLen; ++i) {
            Plcp[i][j] = min(Plcp[i][j - 1], Plcp[i + (1 << (j - 1))][j - 1]);
            for (int t = 0; t < 2; ++t)
                P[t][i][j] = max(P[t][i][j - 1], P[t][i + (1 << (j - 1))][j - 1]);
        }
    }

    stack<int> st;
    for (int i = 2; i <= strLen; ++i) {
        while(sz(st) && getLCP(st.top(), i - 1) >= lcp[i - 1]) {
            int x(st.top()); st.pop();
            int y = (sz(st)) ? st.top() : 0;

            int lcpn = getLCP(x, i - 2);
            int l(1), r(lcpn), opt(0);
            while(l <= r) {
                int mid = (l + r) >> 1;
                int f(-2 * sa[x] - 1);

                if(sa[x] + mid / 2 <= sa[x] + (lcpn - 1) / 2)
                    f = max(f, getMax(P[0], sa[x] + mid / 2, sa[x] + (lcpn - 1) / 2));

                if(sa[x] + (mid - 1) / 2 <= sa[x] + lcpn / 2 - 1)
                    f = max(f, getMax(P[1], sa[x] + (mid - 1) / 2, sa[x] + lcpn / 2 - 1));

                if(f + 2 * sa[x] > 0) {
                    opt = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }

            res = max(res, 1LL * opt * (i - y - 1));
            //cout << i << ' ' << y << ' ' << x << ' ' << lcpn << '\n';
        }

        st.push(i - 1);
    }

    while(sz(st)) {
        int x(st.top()); st.pop();
        int y = (sz(st)) ? st.top() : 0;

        int lcpn = getLCP(x, strLen - 1);
        int l(1), r(lcpn), opt(0);
        while(l <= r) {
            int mid = (l + r) >> 1;
            int f(-2 * sa[x] - 1);

            if(sa[x] + mid / 2 <= sa[x] + (lcpn - 1) / 2)
                f = max(f, getMax(P[0], sa[x] + mid / 2, sa[x] + (lcpn - 1) / 2));

            if(sa[x] + (mid - 1) / 2 <= sa[x] + lcpn / 2 - 1)
                f = max(f, getMax(P[1], sa[x] + (mid - 1) / 2, sa[x] + lcpn / 2 - 1));

            if(f + 2 * sa[x] >= 0) {
                opt = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        res = max(res, 1LL * opt * (strLen - y));
        //cout << strLen + 1 << ' ' << y << ' ' << x << ' ' << lcpn << '\n';
    }

    cout << res << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "palindrome"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    int numTest = 1;
    if(isMultiTest)
        cin >> numTest;

    while(numTest--)
        process();

    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:295:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  295 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:296:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  296 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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