답안 #653340

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653340 2022-10-26T15:12:43 Z longvu Palinilap (COI16_palinilap) C++17
54 / 100
1000 ms 28576 KB
/**
 *    author:  longvu
 *    created: 10/26/22 10:01:42
**/
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
const int INF = numeric_limits<int>::max();
const int nax = (int)(100091);
const int mod = 1234567891;

template<class X, class Y>
bool maximize(X& x, const Y y) {
    if (y > x) {x = y; return true;}
    return false;
}
template<class X, class Y>
bool minimize(X& x, const Y y) {
    if (y < x) {x = y; return true;}
    return false;
}

bool ok(string s) {
    string revs = s;
    reverse(all(revs));
    return (s == revs);
}

int n;
string s;
int sub1() {
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        string t = s;
        for (char j = 'a'; j <= 'z'; ++j) {
            t[i] = j;
            int sum = 0;
            for (int e = 1; e <= n; ++e) {
                for (int f = 1; f <= e; ++f) {
                    if (ok(t.substr(f, e - f + 1))) {
                        sum++;
                    }
                }
            }
            maximize(res, sum);
        }
    }
    return res;
}

int expo(int a, int b) {
    if (!b) {
        return 1;
    }
    int tmp = expo(a, b / 2);
    if (b & 1) {
        return tmp * tmp % mod * (a % mod) % mod;
    }
    return tmp * tmp % mod;
}

const int BASE = (int)(311);
int pw[nax], inv[nax];;
void precal() {
    pw[0] = 1;
    for (int i = 1; i < nax; ++i) {
        pw[i] = BASE * pw[i - 1] % mod;
    }
    inv[nax - 1] = expo(pw[nax - 1], mod - 2);
    for (int i = nax - 2; i >= 0; --i) {
        inv[i] = BASE * inv[i + 1] % mod;
    }
}

int get_hash(int h[], int l, int r) {
    return (h[r] - h[l - 1] + mod) * inv[l - 1] % mod;
}

int h[nax], hrev[nax];
int sub2() {
    precal();
    int res = 0;
    string t = s, revt = s.substr(1);
    reverse(all(revt));
    revt = '$' + revt;
    for (int i = 1; i <= n; ++i) {
        for (char j = 'a'; j <= 'z'; ++j) {
            t[i] = revt[n - i + 1] = j;
            for (int e = 1; e <= n; ++e) {
                h[e] = (t[e] * pw[e] % mod + h[e - 1]) % mod;
            }
            for (int e = 1; e <= n; ++e) {
                hrev[e] = (revt[e] * pw[e] % mod + hrev[e - 1]) % mod;
            }
            int sum = 0;
            for (int e = 1; e <= n; ++e) {
                int l = 1, r = min(e, n - e + 1);
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (get_hash(h, e - mid + 1, e) == get_hash(hrev, n - (e + mid - 1) + 1, n - e + 1)) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                l--;
                sum += l;
            }
            for (int e = 2; e <= n; ++e) {
                if (t[e] == t[e - 1]) {
                    int l = 1, r = min(e - 1, n - e + 1);
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (get_hash(h, e - mid, e - 1) == get_hash(hrev, n - (e + mid - 1) + 1, n - e + 1)) {
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    l--;
                    sum += l;
                }
            }
            maximize(res, sum);
        }
        t[i] = revt[n - i + 1] = s[i];
    }
    return res;
}

struct Fenwick_tree {
    int n, BIT[nax];
    void reseter(int _n) {
        n = _n;
        for (int i = 1; i <= n; ++i) {
            BIT[i] = 0;
        }
    }

    void update(int idx, int val) {
        assert(idx);
        for (int i = idx; i <= n; i += i & (-i)) {
            (BIT[i] += val) %= mod;
        }
    }

    int get(int r) {
        int res = 0;
        for (int i = r; i > 0; i -= i & (-i)) {
            (res += BIT[i]) %= mod;
        }
        return res;
    }
};

#define Fi first
#define Se second

vector<pair<int, int>> memo[nax][2][2];
Fenwick_tree hp, revhp;
int pre[nax][3][2], mp[nax];
int sub3() {
    precal();
    int res = 0;
    string t = s, revt = s.substr(1);
    reverse(all(revt));
    revt = '$' + revt;
    for (int e = 1; e <= n; ++e) {
        h[e] = (t[e] * pw[e] % mod + h[e - 1]) % mod;
    }
    for (int e = 1; e <= n; ++e) {
        hrev[e] = (revt[e] * pw[e] % mod + hrev[e - 1]) % mod;
    }
    int res_base = 0;
    for (int e = 1; e <= n; ++e) {
        int l = 1, r = min(e, n - e + 1);
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (get_hash(h, e - mid + 1, e) == get_hash(hrev, n - (e + mid - 1) + 1, n - e + 1)) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        l--;
        if (l > 1) {
            pre[e - l + 1][0][0]++;
            pre[e][0][0]--;
            pre[e - l + 1][1][0] += e;
            pre[e][1][0] -= e;
            pre[e - l + 1][2][0] += l;
            pre[e][2][0] -= l;
            pre[e + 1][0][1]++;
            pre[e + l][0][1]--;
            pre[e + 1][1][1] += e;
            pre[e + l][1][1] -= e;
            pre[e + 1][2][1] += l;
            pre[e + l][2][1] -= l;
        }
        memo[e - l + 1][0][0].push_back({e, l});
        memo[e + l - 1][0][1].push_back({e, l});
        res_base += l;
    }
    for (int e = 2; e <= n; ++e) {
        if (t[e] == t[e - 1]) {
            int l = 1, r = min(e - 1, n - e + 1);
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (get_hash(h, e - mid, e - 1) == get_hash(hrev, n - (e + mid - 1) + 1, n - e + 1)) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            l--;
            pre[e - l][0][0]++;
            pre[e][0][0]--;
            pre[e - l][1][0] += e - 1;
            pre[e][1][0] -= e - 1;
            pre[e - l][2][0] += l;
            pre[e][2][0] -= l;
            pre[e + 1][0][1]++;
            pre[e + l][0][1]--;
            pre[e + 1][1][1] += e;
            pre[e + l][1][1] -= e;
            pre[e + 1][2][1] += l;
            pre[e + l][2][1] -= l;
            mp[e] = l;
            memo[e - l][1][0].push_back({e, l});
            memo[e + l - 1][1][1].push_back({e, l});
            res_base += l;
        }
    }
    maximize(res, res_base);
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= 2; ++j) {
            for (int e = 0; e <= 1; ++e) {
                pre[i][j][e] += pre[i - 1][j][e];
            }
        }
    }
    hp.reseter(n + 7);
    revhp.reseter(n + 7);
    for (int i = 1; i <= n; ++i) {
        hp.update(i, t[i] * pw[i] % mod);
        revhp.update(i, revt[i] * pw[i] % mod);
    }
    for (int i = 1; i <= n; ++i) {
        for (char j = 'a'; j <= 'z'; ++j) {
            if (j != s[i]) {
                t[i] = revt[n - i + 1] = j;
                hp.update(i, (j * pw[i] % mod - hp.get(i) + hp.get(i - 1) + mod) % mod);
                revhp.update(n - i + 1, (j * pw[n - i + 1] % mod - revhp.get(n - i + 1) + revhp.get(n - i) + mod) % mod);
                auto get_hashp = [&](int l, int r) {
                    return (hp.get(r) - hp.get(l - 1) + mod) * inv[l - 1] % mod;
                };
                auto get_revhashp = [&](int l, int r) {
                    return (revhp.get(r) - revhp.get(l - 1) + mod) * inv[l - 1] % mod;
                };
                int sum = res_base;
                sum -= pre[i][2][0];
                sum += pre[i][1][0] - i * pre[i][0][0];
                sum -= pre[i][2][1];
                sum += i * pre[i][0][1] - pre[i][1][1];
                if (s[i] == s[i + 1]) {
                    sum -= mp[i + 1];
                }
                if (t[i] == t[i + 1]) {
                    int e = i + 1, l = 1, r = min(e - 1, n - e + 1);
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (get_hashp(e - mid, e - 1) == get_revhashp(n - (e + mid - 1) + 1, n - e + 1)) {
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    l--;
                    sum += l;
                }
                if (s[i - 1] == s[i]) {
                    sum -= mp[i];
                }
                if (t[i - 1] == t[i]) {
                    int e = i, l = 1, r = min(e - 1, n - e + 1);
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (get_hashp(e - mid, e - 1) == get_revhashp(n - (e + mid - 1) + 1, n - e + 1)) {
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    l--;
                    sum += l;
                }
                for (auto [e, z] : memo[i - 1][0][1]) {
                    sum -= z;
                    int l = 1, r = min(e, n - e + 1);
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (get_hashp(e - mid + 1, e) == get_revhashp(n - (e + mid - 1) + 1, n - e + 1)) {
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    l--;
                    sum += l;
                }
                for (auto [e, z] : memo[i + 1][0][0]) {
                    sum -= z;
                    int l = 1, r = min(e, n - e + 1);
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (get_hashp(e - mid + 1, e) == get_revhashp(n - (e + mid - 1) + 1, n - e + 1)) {
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    l--;
                    sum += l;
                }
                for (auto [e, z] : memo[i - 1][1][1]) {
                    sum -= z;
                    int l = 1, r = min(e - 1, n - e + 1);
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (get_hashp(e - mid, e - 1) == get_revhashp(n - (e + mid - 1) + 1, n - e + 1)) {
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    l--;
                    sum += l;
                }
                for (auto [e, z] : memo[i + 1][1][0]) {
                    sum -= z;
                    int l = 1, r = min(e - 1, n - e + 1);
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (get_hashp(e - mid, e - 1) == get_revhashp(n - (e + mid - 1) + 1, n - e + 1)) {
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    l--;
                    sum += l;
                }
                maximize(res, sum);
            }
        }
        t[i] = revt[n - i + 1] = s[i];
        hp.update(i, (s[i] * pw[i] % mod - hp.get(i) + hp.get(i - 1) + mod) % mod);
        revhp.update(n - i + 1, (s[i] * pw[n - i + 1] % mod - revhp.get(n - i + 1) + revhp.get(n - i) + mod) % mod);
    }
    return res;
}


const int sub = 1;
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    n = sz(s);
    s = '$' + s;
    if (n <= 50) {
        if (!sub) cout << "Sub1: " << '\n';
        cout << sub1() << '\n';
        if (sub) return 0;
    }
    if (n <= 500) {
        if (!sub) cout << "Sub2: " << '\n';
        cout << sub2() << '\n';
        if (sub) return 0;
    }
    if (!sub) cout << "Sub3: " << '\n';
    cout << sub3() << '\n';
    if (sub) return 0;
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 11184 KB Output is correct
2 Correct 26 ms 11196 KB Output is correct
3 Correct 20 ms 11308 KB Output is correct
4 Correct 18 ms 11204 KB Output is correct
5 Correct 18 ms 11272 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 12260 KB Output is correct
2 Correct 255 ms 12268 KB Output is correct
3 Correct 253 ms 12208 KB Output is correct
4 Correct 115 ms 11716 KB Output is correct
5 Correct 191 ms 12008 KB Output is correct
6 Correct 241 ms 12164 KB Output is correct
7 Correct 182 ms 12084 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1096 ms 28576 KB Time limit exceeded
2 Halted 0 ms 0 KB -