Submission #653501

#	Time	Username	Problem	Language	Result	Execution time	Memory
653501		longvu	Palinilap (COI16_palinilap)	C++14	100 / 100	177 ms	30312 KiB

palinilap

/**
 *    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) {
    assert(l <= 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;
}

#define Fi first
#define Se second

vector<pair<int, int>> memo[nax][2][2];
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];
            }
        }
    }
    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;
                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 = 2, r = min(e - 1, n - e + 1);
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (get_hash(h, e - mid, e - 2) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + 1) + 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 = 2, r = min(e - 1, n - e + 1);
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (get_hash(h, e - mid, e - 2) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + 1) + 1)) {
                            l = mid + 1;
                        } else {
                            r = mid - 1;
                        }
                    }
                    l--;
                    sum += l;
                }
                for (auto [e, z] : memo[i - 1][0][1]) {
                    if (t[i] == t[e - z]) {
                        sum -= z;
                        int x = z + 1, l = x + 1, r = min(e, n - e + 1);
                        while (l <= r) {
                            int mid = (l + r) >> 1;
                            if (get_hash(h, e - mid + 1, e - x) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + x) + 1)) {
                                l = mid + 1;
                            } else {
                                r = mid - 1;
                            }
                        }
                        l--;
                        sum += l;
                    }
                }
                for (auto [e, z] : memo[i + 1][0][0]) {
                    if (t[i] == t[e + z]) {
                        sum -= z;
                        int x = z + 1, l = x + 1, r = min(e, n - e + 1);
                        while (l <= r) {
                            int mid = (l + r) >> 1;
                            if (get_hash(h, e - mid + 1, e - x) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + x) + 1)) {
                                l = mid + 1;
                            } else {
                                r = mid - 1;
                            }
                        }
                        l--;
                        sum += l;
                    }
                }
                for (auto [e, z] : memo[i - 1][1][1]) {
                    if (t[i] == t[e - 1 - z]) {
                        sum -= z;
                        int x = z + 1, l = x + 1, r = min(e - 1, n - e + 1);
                        while (l <= r) {
                            int mid = (l + r) >> 1;
                            if (get_hash(h, e - mid, e - 1 - x) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + x) + 1)) {
                                l = mid + 1;
                            } else {
                                r = mid - 1;
                            }
                        }
                        l--;
                        sum += l;
                    }
                }
                for (auto [e, z] : memo[i + 1][1][0]) {
                    if (t[i] == t[e + z]) {
                        sum -= z;
                        int x = z + 1, l = x + 1, r = min(e - 1, n - e + 1);
                        while (l <= r) {
                            int mid = (l + r) >> 1;
                            if (get_hash(h, e - mid, e - 1 - x) == get_hash(hrev, n - (e + mid - 1) + 1, n - (e + x) + 1)) {
                                l = mid + 1;
                            } else {
                                r = mid - 1;
                            }
                        }
                        l--;
                        sum += l;
                    }
                }
                maximize(res, sum);
            }
        }
        t[i] = revt[n - i + 1] = s[i];
    }
    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 <= 100) {
    //     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;
}

Compilation message (stderr)

palinilap.cpp: In function 'long long int sub3()':
palinilap.cpp:262:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  262 |                 for (auto [e, z] : memo[i - 1][0][1]) {
      |                           ^
palinilap.cpp:278:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  278 |                 for (auto [e, z] : memo[i + 1][0][0]) {
      |                           ^
palinilap.cpp:294:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  294 |                 for (auto [e, z] : memo[i - 1][1][1]) {
      |                           ^
palinilap.cpp:310:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  310 |                 for (auto [e, z] : memo[i + 1][1][0]) {
      |                           ^

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 46 / 46