Submission #368323

#	Time	Username	Problem	Language	Result	Execution time	Memory
368323		TruaShamu	Palinilap (COI16_palinilap)	Java	100 / 100	613 ms	68532 KiB

palinilap

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class palinilap {
    public static long M = (long) 1e9 + 9;
    public static int P = 9973;
    public static int N;
    public static char[][] s;
    public static long[][] hsh = new long[2][210001];
    public static long[] pw = new long[210001];
    public static long[][] extra = new long[210001][26];
    public static long[] numPalindromes = new long[210001];
    public static int[] deltaDelta = new int[210001];


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String tmp = br.readLine();
        s = new char[2][(tmp.length() * 2) + 1];
        for (int i = 0; i < tmp.length(); i++) {
            s[0][i * 2] = '#';
            s[0][i * 2 + 1] = tmp.charAt(i);
        }

        s[0][tmp.length() * 2] = '#';
        N = s[0].length;
        s[1] = s[0];


        s[1] = reverse(s[1]);


        hsh[0][0] = 1;
        hsh[1][0] = 1;
        pw[0] = 1;
        for (int i = 0; i < N; i++) {
            hsh[0][i + 1] = ((hsh[0][i] * P) % M + s[0][i]) % M;
            hsh[1][i + 1] = ((hsh[1][i] * P) % M + s[1][i]) % M;
            pw[i + 1] = pw[i] * P % M;
        }

        long base = 0;
        for (int i = 0; i < N; i++) {
            // calculate radius of palindrome
            int lo = 0, hi = Integer.min(i, N - i - 1) + 1, r = 0;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                boolean valid = getHash(i - mid, i, 0) == getHash(i, i + mid, 1);

                if (valid) {
                    r = mid;
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            if (r != 0) {
                deltaDelta[i - r]++;
                deltaDelta[i + 1] -= 2;
                deltaDelta[i + r + 2]++;
            }
            base += (r + 1) / 2;
            for (int j = 0; j < 26; j++) extra[i][j] += (r + 1) / 2;

            int x = i - r - 1, y = i + r + 1;
            if (x < 0 || x >= N || y < 0 || y >= N) continue;

            // fix the boundary, calculate the new radius of palindrome
            lo = 0;
            hi = Integer.min(i - r - 1, N - (i + r + 1) - 1) + 1;
            int r2 = 0;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                boolean valid = getHash(i - r - 1 - mid, i - r - 2, 0) == getHash(i + r + 2, i + r + 1 + mid, 1);

                if (valid) {
                    r2 = mid;
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            r2++;

            assert (s[0][x] != '#' && s[1][y] != '#');
            extra[x][s[0][y] - 'a'] += r2 / 2;
            extra[y][s[0][x] - 'a'] += r2 / 2;
        }

        long delta = 0, tot = 0;
        for (int i = 0; i < N; i++) {
            delta += deltaDelta[i];
            tot += delta;
            numPalindromes[i] = tot / 2;
        }

        long best = 0;
        for (int i = 0; i < N; i++) {
            if (i % 2 == 1) {
                for (int j = 0; j < 26; j++) {
                    best = Long.max(best, extra[i][j] - numPalindromes[i]);
                }
            }
        }
        long answer = base + best;
        System.out.println(answer);

        System.exit(0);
    }

    public static long getHash(int a, int b, int c) {
        assert (a >= 0 && a < N && b >= 0 && b < N);
        if (c == 1) {
            int tmp = a;
            a = N - 1 - b;
            b = N - 1 - tmp;
        }
        return (hsh[c][b + 1] - (hsh[c][a] * pw[b - a + 1]) % M + M) % M;
    }


    public static char[] reverse(char a[]) {
        char[] b = new char[a.length];
        int j = a.length;
        for (int i = 0; i < a.length; i++) {
            b[j - 1] = a[i];
            j = j - 1;
        }
        return b;
    }


}

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