oj.uz

Submission #368323

# Submission time Handle Problem Language Result Execution time Memory
368323 2021-02-19T22:12:26 Z TruaShamu Palinilap (COI16_palinilap) Java 11
100 / 100
 613 ms 68532 KB 
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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 63452 KB Output is correct
2 Correct 168 ms 63444 KB Output is correct
3 Correct 170 ms 63340 KB Output is correct
4 Correct 161 ms 63484 KB Output is correct
5 Correct 177 ms 63348 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 66856 KB Output is correct
2 Correct 257 ms 66560 KB Output is correct
3 Correct 277 ms 66412 KB Output is correct
4 Correct 224 ms 66288 KB Output is correct
5 Correct 235 ms 66068 KB Output is correct
6 Correct 244 ms 65984 KB Output is correct
7 Correct 272 ms 66560 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 68312 KB Output is correct
2 Correct 518 ms 68392 KB Output is correct
3 Correct 554 ms 68332 KB Output is correct
4 Correct 587 ms 68532 KB Output is correct
5 Correct 573 ms 68268 KB Output is correct
6 Correct 567 ms 68232 KB Output is correct
7 Correct 568 ms 68316 KB Output is correct
8 Correct 471 ms 67808 KB Output is correct
9 Correct 600 ms 68316 KB Output is correct
10 Correct 557 ms 68236 KB Output is correct
11 Correct 514 ms 68360 KB Output is correct
12 Correct 569 ms 68384 KB Output is correct
13 Correct 603 ms 68356 KB Output is correct
14 Correct 613 ms 68416 KB Output is correct
15 Correct 608 ms 68268 KB Output is correct
16 Correct 559 ms 68440 KB Output is correct
17 Correct 565 ms 68372 KB Output is correct
18 Correct 612 ms 68212 KB Output is correct
19 Correct 563 ms 68396 KB Output is correct