Submission #249112

#	Time	Username	Problem	Language	Result	Execution time	Memory
249112		kingfran1907	Palinilap (COI16_palinilap)	C++14	100 / 100	270 ms	396028 KiB

palinilap

#include <bits/stdc++.h>

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const llint base = 9973;
const llint mod = 1e9+9;

int n;
char niz[maxn];
llint phas[maxn], shas[maxn];
llint pot[maxn];
llint chn[maxn][500];
llint pre[maxn], los[maxn];

llint pget(int x, int y) {
    y++;
    return (phas[y] - (phas[x] * pot[y - x]) % mod + mod) % mod;
}

llint sget(int x, int y) {
    y++;
    return (shas[x] - (shas[y] * pot[y - x]) % mod + mod) % mod;
}

int main() {
    scanf("%s", niz); n = strlen(niz);

    pot[0] = 1;
    for (int i = 1; i <= n; i++) pot[i] = pot[i - 1] * base, pot[i] %= mod;
    for (int i = 0; i < n; i++)
        phas[i + 1] = (phas[i] * base) % mod + niz[i], phas[i + 1] %= mod;

    for (int i = n; i > 0; i--)
        shas[i - 1] = (shas[i] * base) % mod + niz[i - 1], shas[i - 1] %= mod;

    llint sol = 0;
    for (int i = 0; i < n; i++) {
        int lo = 0;
        int hi = n;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            int l = i - mid;
            int r = i + mid;

            //printf("mid: %d\n", mid);
            if (l < 0 || r >= n) hi = mid - 1;
            else if (pget(l, r) == sget(l, r)) lo = mid;
            else hi = mid - 1;
        }
        sol += lo + 1;
        int l = i - lo;
        int r = i + lo;

        int clo = lo;
        if (!(l == 0 || r == n - 1)) {
            char dx = niz[l - 1], dy = niz[r + 1];

            lo = 0, hi = n;
            while (lo < hi) {
                int mid = (lo + hi + 1) / 2;
                int dl = l - mid - 1;
                int dr = r + mid + 1;

                if (dl < 0 || dr >= n) hi = mid - 1;
                else if (pget(dl, l - 2) == sget(r + 2, dr)) lo = mid;
                else hi = mid - 1;
            }
            chn[l - 1][dy] += lo + 1;
            chn[r + 1][dx] += lo + 1;
        }

        lo = clo;
        if (lo == 0) continue;

        pre[l]++;
        pre[i] -= lo + 1;
        pre[i + 1] += 2 * lo;
        pre[i + 2] -= lo + 1;
        pre[r + 2]++;
    }

    for (int i = 1; i < n; i++) {
        if (niz[i - 1] != niz[i]) continue;
        int lo = 0;
        int hi = n;

        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            int l = i - mid - 1;
            int r = i + mid;

            if (l < 0 || r >= n) hi = mid - 1;
            else if (pget(l, r) == sget(l, r)) lo = mid;
            else hi = mid - 1;
        }
        sol += lo + 1;

        int l = i - 1 - lo;
        int r = i + lo;

        pre[l]++;
        pre[i]--;
        pre[i + 1]--;
        pre[r + 2]++;

        if (l == 0 || r == n - 1) continue;
        char dx = niz[l - 1], dy = niz[r + 1];

        lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            int dl = l - mid - 1;
            int dr = r + mid + 1;

            if (dl < 0 || dr >= n) hi = mid - 1;
            else if (pget(dl, l - 2) == sget(r + 2, dr)) lo = mid;
            else hi = mid - 1;
        }
        chn[l - 1][dy] += lo + 1;
        chn[r + 1][dx] += lo + 1;
    }

    for (int i = 1; i < n; i++) {
        if (niz[i - 1] == niz[i]) continue;

        int lo = 0;
        int hi = n;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;

            int l = i - 1 - mid;
            int r = i + mid;
            if (l < 0 || r >= n) hi = mid - 1;
            else if (pget(l, i - 2) == sget(i + 1, r)) lo = mid;
            else hi = mid - 1;
        }
        //printf("debug: %d %d\n", i, lo);
        chn[i - 1][niz[i]] += lo + 1;
        chn[i][niz[i - 1]] += lo + 1;
    }

    for (int i = 1; i < n; i++) pre[i] += pre[i - 1];
    los[0] = pre[0];
    for (int i = 1; i < n; i++) los[i] = los[i - 1] + pre[i];

    //printf("los: ");
    //for (int i = 0; i < n; i++) printf("%lld ", los[i]);
    //printf("\n");

    /**
    printf("chn:\n");
    for (int i = 'a'; i < 'd'; i++) {
        for (int j = 0; j < n; j++) {
            printf("%lld ", chn[j][i]);
        }
        printf("\n");
    }
    **/

    llint bes = 0;
    for (int i = 0; i < n; i++) {
        for (char j = 'a'; j <= 'z'; j++) {
            if (j != niz[i])
                bes = max(bes, chn[i][j] - los[i]);
        }
    }
    printf("%lld\n", sol + bes);
    return 0;
}

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:70:26: warning: array subscript has type 'char' [-Wchar-subscripts]
             chn[l - 1][dy] += lo + 1;
                          ^
palinilap.cpp:71:26: warning: array subscript has type 'char' [-Wchar-subscripts]
             chn[r + 1][dx] += lo + 1;
                          ^
palinilap.cpp:121:22: warning: array subscript has type 'char' [-Wchar-subscripts]
         chn[l - 1][dy] += lo + 1;
                      ^
palinilap.cpp:122:22: warning: array subscript has type 'char' [-Wchar-subscripts]
         chn[r + 1][dx] += lo + 1;
                      ^
palinilap.cpp:140:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         chn[i - 1][niz[i]] += lo + 1;
                          ^
palinilap.cpp:141:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         chn[i][niz[i - 1]] += lo + 1;
                          ^
palinilap.cpp:166:40: warning: array subscript has type 'char' [-Wchar-subscripts]
                 bes = max(bes, chn[i][j] - los[i]);
                                        ^
palinilap.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", niz); n = strlen(niz);
     ~~~~~^~~~~~~~~~~

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