Submission #966189

#	Time	Username	Problem	Language	Result	Execution time	Memory
966189		vjudge1	Palinilap (COI16_palinilap)	C++17	0 / 100	149 ms	29564 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

struct Hash {
    int n;
    string s;
    const ll p = 31, mod = 1e9 + 7;
    vector<ll> pw, hash;

    Hash(string _s) : s(_s) {
        n = s.size();
        pw.resize(n+1);
        hash.resize(n+1);
        pw[0] = 1;
        for(int i=1; i<=n; i++) pw[i] = (pw[i-1] * p) % mod;
        hash[0] = s[0] - 'a' + 1;
        for(int i=1; i<n; i++) hash[i] = (hash[i-1] + pw[i] * (s[i] - 'a' + 1)) % mod;
    }

    ll getHash(int l, int r) { return (hash[r] - (l ? hash[l-1] : 0) + mod) % mod; }

    ll getHash(int l, int r, int p, char ch) {
        ll ans = getHash(l, r);
        ans = (ans + pw[p] * (ch - 'a' + 1) - pw[p] * (s[p] - 'a' + 1) + mod) % mod;
        return ans;
    }

    bool equal(int l1, int r1, int l2, int r2) {
        if(r1 - l1 != r2 - l2) return 0;
        if(l1 > l2) swap(l1, l2), swap(r1, r2);
        return (pw[l2-l1] * getHash(l1, r1) % mod) == getHash(l2, r2);
    }

    bool isPal(int l, int r) {
        return equal(l, r, n-1-r, n-1-l);
    }

    bool isPal(int l, int r, int p, char ch) {
        int l2=n-1-r, r2=n-1-l;
        ll h1 = getHash(l, r, p, ch);
        ll h2 = getHash(n-1-r, n-1-l, n-1-p, ch);
        return (pw[l2-l] * h1 % mod) == h2; 
    }
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
   
    string s;
    cin >> s;
    int n = s.size();
    ll ans = 0, ans2 = 0;

    string s2 = s; reverse(s2.begin(), s2.end());
    s += s2;

    Hash H(s);
    
    //neparna dolzina
    int C[n][26], D[2][n+1];
    memset(C, 0, sizeof(C));
    memset(D, 0, sizeof(D));
    vector<pair<int, int> > R[2];
    for(int i=0; i<n; i++) {
        int L = min(i, n-1-i);
        int l=0, r=L, len=0;

        while(l <= r) {
            int mid = (l + r) / 2;
            if(H.isPal(i-mid, i+mid)) len = mid, l = mid + 1;
            else r = mid - 1;
        }

        if(len) {
            R[0].push_back({ i - len, i - 1 });
            //cout << "remove left " << i - len << " " << i-1 << '\n';
            R[1].push_back({ i + 1, i + len });
            //cout << "remove right " << i+1 << " " << i+len << '\n';
        }

        //cout << i << ": " << len << '\n';

        if(i - len - 1 >= 0 && i + len + 1 < n) {
            l=len+1, r=L;
            int len2=0;
            while(l <= r) {
                int mid = (l + r) / 2;
                if(H.isPal(i-mid, i+mid, i-len-1, s[i+len+1])) len2 = mid, l = mid + 1;
                else r = mid - 1;
            }
            //cout << len2 << '\n';
            //cout << "add " << len2 - len << " on " << i-len-1 << " " << i+len+1 << '\n';
            C[i-len-1][s[i+len+1]-'a'] += len2 - len;
            C[i+len+1][s[i-len-1]-'a'] += len2 - len;
        }

        ans2 += len + 1;
    }

    for(int i=0; i<n-1; i++) {
        int L = min(i, n-2-i);
        int l=0, r=L, len=0;

        while(l <= r) {
            int mid = (l + r) / 2;
            if(H.isPal(i-mid, i+1+mid)) len = mid, l = mid + 1;
            else r = mid - 1;
        }

        //cout << i << ": " << len << '\n';

        if(H.isPal(i, i+1)) {
            R[0].push_back({ i - len, i });
            //cout << "remove left " << i-len << " " << i << '\n';
            R[1].push_back({ i + 1, i + len + 1 });
            //cout << "remove right " << i+1 << " " << i+len+1 << '\n';

            if(i-len-1 >= 0 && i+len+2 < n) {
                l=len+1, r=L;
                int len2 = 0;
                
                while(l <= r) {
                    int mid = (l + r) / 2;
                    if(H.isPal(i-mid, i+mid+1, i-len-1, s[i+len+2])) len2 = mid, l = mid + 1;
                    else r = mid - 1;
                }

                //cout << len2 << " (0)" << '\n';
                //cout << "add " << len2 - len << " on " << i-len-1 << " " << i+len+2 << '\n';
                C[i-len-1][s[i+len+2]-'a'] += len2 - len;
                C[i+len+2][s[i-len-1]-'a'] += len2 - len;
            }

            ans2 += len + 1;
        } else {
            l=0, r=L;
            int len2=0;

            while(l <= r) {
                int mid = (l + r) / 2;
                if(H.isPal(i-mid, i+mid+1, i, s[i+1])) len2 = mid, l = mid + 1;
                else r = mid - 1;
            }

            //cout << len2 << " (1)" << '\n';
            //cout << "add " << len2 + 1 << " on " << i << " " << i+1 << '\n';
            C[i][s[i+1]-'a'] += len2 + 1;
            C[i+1][s[i]-'a'] += len2 + 1;
        }
    }

    for(int i=0; i<2; i++) {
        if(i == 1) for(auto &x : R[i]) x = { n - x.second - 1, n - x.first - 1};
        //for(auto &x : R[i]) cout << x.first << " " << x.second << '\n';
        for(auto &x : R[i]) D[i][x.first]++, D[i][x.second+1]--;
        for(int j=1; j<=n; j++) D[i][j] += D[i][j-1];
        for(auto &x : R[i]) D[i][x.second+1] -= x.second - x.first + 1;
        for(int j=1; j<=n; j++) D[i][j] += D[i][j-1];
        if(i) reverse(D[i], D[i] + n);
        //for(int j=0; j<n; j++) cout << D[i][j] << " ";
        //cout << '\n';
    }

    for(int i=0; i<n; i++)
        for(int j=0; j<26; j++)
            if(s[i] - 'a' != j) ans = max(ans, ans2 - D[0][i] - D[1][i] + C[i][j]);
    cout << max(ans, ans2) << '\n';
    return 0;
}

Compilation message (stderr)

palinilap.cpp: In member function 'bool Hash::isPal(long long int, long long int, long long int, char)':
palinilap.cpp:44:23: warning: unused variable 'r2' [-Wunused-variable]
   44 |         int l2=n-1-r, r2=n-1-l;
      |                       ^~

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