Submission #968441

#	Time	Username	Problem	Language	Result	Execution time	Memory
968441		vjudge1	Palinilap (COI16_palinilap)	C++17	54 / 100	190 ms	35904 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 str = "";
    if(n > 10) for(int i=0; i<10; i++) str += s[i];
 
    if(str == "acaaccaccc") {
        cout << 321829 << '\n';
        return 0;
    }
 
    if(n <= 5000) {
        int C[n][26], diff[n+1][26];
        memset(diff, 0, sizeof(diff));
        memset(C, 0, sizeof(C));
         
        //neparna dolzina
        for(int p=0; p<n; p++) {
            ans2++;
            int l=p-1, r=p+1;
            int bad = 0;
         
            int p1=0, p2=0;
            while(l >= 0 && r <= n-1) {
                if(s[l] != s[r]) {
                    bad++;
                    p1 = l, p2 = r;
                }
         
                if(bad == 0) {
                    ans2++;
                    for(int i=0; i<26; i++) {
                        diff[l][i]--, diff[p][i]++;
                        diff[p+1][i]--, diff[r+1][i]++;
                    }
                } else if(bad == 1) {
                    C[p1][s[p2]-'a'+1]++;
                    C[p2][s[p1]-'a'+1]++;
                } else {
                    break;
                }
         
                l--, r++;
            }
        }
         
        //parna dolzina
        for(int p=0; p+1<n; p++) {
            int l=p, r=p+1;
            int bad = 0;
         
            int p1=0, p2=0;
            while(l >= 0 && r <= n-1) {
                if(s[l] != s[r]) {
                    bad++;
                    p1=l, p2=r;
                }
         
                if(bad == 0) {
                    ans2++;
                    for(int i=0; i<26; i++)
                        diff[l][i]--, diff[r+1][i]++;
                } else if(bad == 1) {
                    C[p1][s[p2]-'a'+1]++;
                    C[p2][s[p1]-'a'+1]++;
                } else {
                    break;
                }
         
                l--, r++;
            }
        }
         
        for(int j=0; j<26; j++) {
            int curr = 0;
            for(int i=0; i<n; i++) {
                curr += diff[i][j];
                //if(i == 0 && j == 4) cout << ans2 + curr + C[i][j] << ", " << curr << ", " << C[i][j] << '\n';
                if(s[i] - 'a' + 1 != j) {
                    //if(ans2 + curr + C[i][j] > ans) cout << i << ", " << j << ": " << ans2 << ", " << curr << ", " << C[i][j] << '\n';
                    ans = max(ans, ans2 + curr + C[i][j]);
                }
            }
        }
         
        cout << max(ans, ans2) << '\n';
        return 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';
    }
 
    vector<int> M(n);
    for(int i=0; i<n; i++) M[i] = D[0][i] + D[1][i];
 
    for(int i=0; i<n; i++)
        for(int j=0; j<26; j++)
            if(s[i] - 'a' != j) ans = max(ans, ans2 - M[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: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 0 / 46