Submission #1242032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242032		Mike_Vu	Palinilap (COI16_palinilap)	C++17	17 / 100	62 ms	26032 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define BITJ(x, j) (((x)>>(j))&1)
#define MASK(j) (1LL<<(j))
#define ALL(v) v.begin(), v.end()

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

namespace modulofunc{
    const int mod = 998244353;
    int add(int x, int y) {
        return (mod-x <= y ? x-mod+y : x+y);
    }
    void addt(int &x, int y) {
        x = add(x, y);
    }
    int sub(int x, int y) {
        return (x-y < 0 ? x-y+mod : x-y);
    }
    void subt(int &x, int y) {
        x = sub(x, y);
    }
    int mul(int x, int y) {
        return 1LL*x*y%mod;
    }
    int binpow(int x, int k) {
        int res = 1;
        while (k > 0 ){
            if (k&1) res = mul(res, x);
            x = mul(x, x);
            k >>= 1;
        }
        return res;
    }
}
using namespace modulofunc;

const int maxn = 1e5+5;
int n;
string s;

namespace sub1{
    int ans = 0, curans;
    void checkvar() {
        curans = 0;
        for (int i = 1; i <= n; i++) {
            //on ele
            curans++;
            int len;
            for (len = 1; len <= min(i-1, n-i); len++){
                if (s[i-len] != s[i+len]) {
                    break;
                }
            }
            --len;
//            cout << "on ele " << i << ' ' << len << "\n";
            curans += len;
        }
        for (int i = 1; i < n; i++) {
            //in mid
            int len;
            for (len = 1; len <= min(i, n-i); len++) {
                if (s[i-len+1] != s[i+len]) {
                    break;
                }
            }
            --len;
//            cout << "in mid " << i << ' ' << len << "\n";
            curans += len;
        }
        maximize(ans, curans);
    }
    void solve() {
        for (int i = 1; i <= n; i++) {
            for (int c = 0; c < 26; c++) {
                char temp = s[i];
                s[i] = c+'a';
//                cout << "[] changing " << i << ' ' << char(c+'a') << "\n";
                checkvar();
                s[i] = temp;
            }
        }
        cout << ans;
    }
}

namespace sub3{
    const int base = 31;
    int pw[maxn], prefh[maxn][2];
    void setup() {
        pw[0] = 1;
        for (int i= 1; i < maxn; i++) {
            pw[i] = mul(pw[i-1], base);
//            if (i < 7) cout << pw[i] << ' ';
        }
//        cout << "\n";
        prefh[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            prefh[i][0] = add(mul(prefh[i-1][0], base), (int)(s[i]-'a'+1));
        }
        prefh[n+1][1] = 0;
        for (int i = n; i; i--) {
            prefh[i][1] = add(mul(prefh[i+1][1], base), (int)(s[i]-'a'+1));
        }
//        cout << "here comes all prefh\n";
//        for (int i = 1; i <= n; i++) {
//            cout << prefh[i][0] << ' ';
//        }
//        cout << "\n";
//        for (int i = 1; i <= n; i++) {
//            cout << prefh[i][1] << ' ';
//        }
//        cout << "\n";
    }
    int gethash(int l, int r, bool rev) {
        int val;
        if (rev) val = sub(prefh[l][1], mul(prefh[r+1][1], pw[r-l+1]));
        else val = sub(prefh[r][0], mul(prefh[l-1][0], pw[r-l+1]));
//        cout << "gethash " << l << ' ' << r << ' ' << rev << ": " << val << "\n";
        return val;
    }

    struct segment{
        int l, r;
        bool inmid;
        segment(int _l, int _r, bool _inmid) {
            l = _l;
            r = _r;
            inmid = _inmid;
        }
    };
    vector<segment> realseg;
    ll incdelta[maxn], stadelta[maxn]; //delta encoding
    ll preans;
    ll anschange[maxn][26];
    ll ans;
    void construct_boundaries() {
        //setup boundaries
        //also calculate preans
        preans = 0;
        for (int i = 1; i <= n; i++) {
            //on element
            //bound of starting segment would be the mid
            int len = 0;
            for (int cnt = n>>1; cnt > 0; cnt >>= 1 ){
                while (len+cnt <= min(n-i, i-1) &&
                       gethash(i-(len+cnt), i, 1) == gethash(i, i+(len+cnt), 0)) {
                    len += cnt;
                }
            }
            //segments: i-len, i+len
            realseg.pb(segment(i-len, i+len, 0));
            preans += len+1;
//            cout << "on ele " << i << ' ' << len+1 << "\n";
        }
        for (int i = 1; i < n; i++) {
            //in mid
            int len = 0;
            for (int cnt = n>>1; cnt > 0; cnt >>= 1) {
                while (cnt+len <= min(i, n-i) &&
                       gethash(i-(len+cnt)+1, i, 1) == gethash(i+1, i+(len+cnt), 0)) {
                    len += cnt;
               }
            }
            //segment: i-len+1, i+len
            realseg.pb(segment(i-len+1, i+len, 1));
            preans += len;
//            cout << "in mid " << i << ' ' << len << "\n";
        }
        ans = preans;
    }
    int check_further(int l, int r) {
        if (l < 1 || r > n) return 0;
        int len = 0;
        for (int cnt = n>>1; cnt > 0; cnt >>= 1){
            while (len+cnt <= min(l, n-r+1) &&
                   gethash(l-(len+cnt)+1, l, 1) == gethash(r, r+(len+cnt)-1, 0)) {
                len += cnt;
           }
        }
        return len;
    }
    void solve() {
        setup();
        construct_boundaries();
        memset(anschange, 0, sizeof(anschange));
        memset(incdelta, 0, sizeof(incdelta));
        memset(stadelta, 0, sizeof(stadelta));
        //case add
        for (segment cur : realseg) {
            int l = cur.l, r = cur.r;
            //delta encoding
            int mid = (l+r)>>1;
            if (cur.inmid) {
                if (r-l > 0) {
                    //inmid
                    incdelta[l-1]++;
                    incdelta[mid]--;
                    incdelta[mid+1]--;
                    incdelta[r]++;
                }
            }
            else if (r-l > 1) {
                //in ele
                //->0<-
                incdelta[l-1]++;
                incdelta[mid-1]--;
                stadelta[mid-1] = l-mid;
                stadelta[mid] = mid-l;
                incdelta[mid+1]--;
                incdelta[r]++;
            }
            //eligible
            if (l <= 1 || r >= n) continue;
            //change left
            //change right
            int val = check_further(l-2, r+2)+1;
//            cout << "[] segment " << l << ' ' << r << ' ' << val << "\n";
            anschange[l-1][s[r+1]-'a'] += val;
            anschange[r+1][s[l-1]-'a'] += val;
        }
        //case minus
        //resolve encoding to ans
        ll curcou = 0, curinc = incdelta[0];
        for (int i = 1; i <= n; i++) {
            curcou += curinc;
            //fixed for i
            for (int c = 0; c < 26; c++) {
                anschange[i][c] -= curcou;
                //maximize ans
                maximize(ans, preans + anschange[i][c]);
            }
            curcou += stadelta[i];
            curinc += incdelta[i];
        }
        cout << ans;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> s;
    n = (int)s.size();
    s = "#"+s;
    if (n <= 100) return sub1::solve(), 0;
    return sub3::solve(), 0;
}
/*
aaaa
10

baccb
9

slavko
7
*/

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