oj.uz

Submission #969000

# Submission time Handle Problem Language Result Execution time Memory
969000 2024-04-24T11:02:53 Z Nhoksocqt1 Palindromes (APIO14_palindrome) C++17
100 / 100
 491 ms 91312 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25688 KB Output is correct
2 Correct 7 ms 27740 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 6 ms 26080 KB Output is correct
5 Correct 6 ms 25692 KB Output is correct
6 Correct 6 ms 27736 KB Output is correct
7 Correct 6 ms 25692 KB Output is correct
8 Correct 6 ms 27740 KB Output is correct
9 Correct 6 ms 25692 KB Output is correct
10 Correct 8 ms 27740 KB Output is correct
11 Correct 8 ms 27740 KB Output is correct
12 Correct 7 ms 27740 KB Output is correct
13 Correct 6 ms 27740 KB Output is correct
14 Correct 6 ms 27920 KB Output is correct
15 Correct 7 ms 27996 KB Output is correct
16 Correct 6 ms 25688 KB Output is correct
17 Correct 7 ms 27740 KB Output is correct
18 Correct 6 ms 25688 KB Output is correct
19 Correct 6 ms 25692 KB Output is correct
20 Correct 6 ms 25860 KB Output is correct
21 Correct 6 ms 25692 KB Output is correct
22 Correct 6 ms 27740 KB Output is correct
23 Correct 6 ms 27740 KB Output is correct
24 Correct 6 ms 27820 KB Output is correct
25 Correct 6 ms 27740 KB Output is correct
26 Correct 7 ms 27740 KB Output is correct
27 Correct 6 ms 25948 KB Output is correct
28 Correct 6 ms 27740 KB Output is correct
29 Correct 6 ms 27740 KB Output is correct
30 Correct 6 ms 27740 KB Output is correct
31 Correct 6 ms 27740 KB Output is correct
32 Correct 6 ms 27740 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25948 KB Output is correct
2 Correct 6 ms 25948 KB Output is correct
3 Correct 7 ms 27904 KB Output is correct
4 Correct 7 ms 27740 KB Output is correct
5 Correct 6 ms 27912 KB Output is correct
6 Correct 7 ms 27740 KB Output is correct
7 Correct 6 ms 25832 KB Output is correct
8 Correct 7 ms 25864 KB Output is correct
9 Correct 7 ms 27740 KB Output is correct
10 Correct 6 ms 27740 KB Output is correct
11 Correct 7 ms 27908 KB Output is correct
12 Correct 7 ms 27740 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32600 KB Output is correct
2 Correct 12 ms 32456 KB Output is correct
3 Correct 14 ms 34140 KB Output is correct
4 Correct 13 ms 34140 KB Output is correct
5 Correct 13 ms 32620 KB Output is correct
6 Correct 13 ms 34140 KB Output is correct
7 Correct 12 ms 34140 KB Output is correct
8 Correct 10 ms 34136 KB Output is correct
9 Correct 9 ms 34136 KB Output is correct
10 Correct 13 ms 34136 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 51536 KB Output is correct
2 Correct 93 ms 51460 KB Output is correct
3 Correct 97 ms 53224 KB Output is correct
4 Correct 103 ms 53068 KB Output is correct
5 Correct 102 ms 51280 KB Output is correct
6 Correct 108 ms 51436 KB Output is correct
7 Correct 93 ms 52816 KB Output is correct
8 Correct 59 ms 53080 KB Output is correct
9 Correct 88 ms 52812 KB Output is correct
10 Correct 116 ms 53044 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 90804 KB Output is correct
2 Correct 267 ms 90288 KB Output is correct
3 Correct 333 ms 91312 KB Output is correct
4 Correct 329 ms 90544 KB Output is correct
5 Correct 401 ms 90288 KB Output is correct
6 Correct 305 ms 90324 KB Output is correct
7 Correct 326 ms 90316 KB Output is correct
8 Correct 200 ms 90288 KB Output is correct
9 Correct 205 ms 90192 KB Output is correct
10 Correct 491 ms 90288 KB Output is correct
11 Correct 328 ms 90308 KB Output is correct
12 Correct 274 ms 90292 KB Output is correct