Submission #1210566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210566		uranium235	Palinilap (COI16_palinilap)	Java	54 / 100	1095 ms	39980 KiB

palinilap

// package ojuz;

import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

public class palinilap {
    public static final long m = (1L << 61) - 1, b = ThreadLocalRandom.current().nextLong(m - 1);
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String s = reader.readLine();
        int n = s.length();

        Hash hash = new Hash(s);
        int l = 0, r = 0;
        long base = 0;
        long[][] buffs = new long[n][26];
        long[] nerfs = new long[n];
        while (r < n) {
            int bound = Math.min(l + 1, n - r);
            int best = hash.palindrome(l, r);
            base += best;
            // the letters that break the palindrome
            int left = l - best;
            int right = r + best;
            // if palindrome can be extended
            if (best < bound) {
                // swap the positions if length is even and letters dont match
                int add = 1 + ((left > 0 && right < n - 1) ? hash.palindrome(left - 1, right + 1) : 0);
                // change the right side to the left, or vice versa leads to more palindromes
                buffs[left][s.charAt(right) - 'a'] += add;
                buffs[right][s.charAt(left) - 'a'] += add;
            }
            for (int i = left + 1; i < l + (l == r ? 0 : 1); i++) nerfs[i] += (i - left);
            for (int i = right - 1; i > r - (l == r ? 0 : 1); i--) nerfs[i] += (right - i);

            if (l < r) l++;
            else r++;
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long max = 0;
            for (long j : buffs[i]) max = Math.max(max, j);
            ans = Math.max(ans, max - nerfs[i]);
        }

        System.out.println(base + ans);
    }

    public static long mult(long a, long b) {
        long low = a * b;
        return ((low & m) + ((Math.multiplyHigh(a, b) << 3) | (low >>> 61))) % m;
    }

    static class Hash {
        public final String s;
        public final long[] pows, hash, rash;
        public Hash(String s) {
            this.s = s;
            this.pows = new long[s.length() + 1];
            pows[0] = 1;
            for (int i = 1; i < pows.length; i++) pows[i] = mult(b, pows[i - 1]);
            this.hash = new long[s.length() + 1];
            for (int i = 1; i < hash.length; i++) hash[i] = (mult(b, hash[i - 1]) + s.charAt(i - 1)) % m;
            this.rash = new long[s.length() + 1];
            for (int i = rash.length - 2; i >= 0; i--) rash[i] = (mult(b, rash[i + 1]) + s.charAt(i)) % m;
        }

        public long hash(int a, int b) {
            return (hash[b + 1] - mult(hash[a], pows[b - a + 1]) + m) % m;
        }

        public long rash(int a, int b) {
            return (rash[a] - mult(rash[b + 1], pows[b - a + 1]) + m) % m;
        }

        public int palindrome(int l, int r) {
            if (s.charAt(l) != s.charAt(r)) return 0;
            // longest "palindrome" from l going left and from r going right
            int hi = Math.min(l + 1, s.length() - r);
            int lo = 0;
            while (lo < hi) {
                int mid = lo + (hi - lo + 1) / 2;
                if (hash(r, r + mid - 1) == rash(l - mid + 1, l)) lo = mid;
                else hi = mid - 1;
            }
            return lo;
        }
    }
}

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