Submission #337461

#	Time	Username	Problem	Language	Result	Execution time	Memory
337461		wolf	Palinilap (COI16_palinilap)	C++14	46 / 100	397 ms	27424 KiB

palinilap

#include <bits/stdc++.h>

using namespace std;

#include <bits/stdc++.h>

using namespace std;

class HASH {
    int mod, base;
    vector<int> p = {1} , hashes = {0};

    int mul(int a , int b) {
        return a * 1ll * b % mod;
    }

    int add(int a , int b) {
        a += b;
        while (a >= mod) a -= mod;
        while (a < 0) a += mod;
        return a;
    }

public:
    HASH(int _mod , int _base) : mod(_mod), base(_base) {}

    void push_back(int x) {
        hashes.push_back(add(mul(hashes.back() , base) , x));
        p.push_back(mul(p.back() , base));
    }

    int get(int l , int r) {
        assert(r + 1 < hashes.size());
        return add(hashes[r + 1] , -mul(p[r - l + 1] , hashes[l]));
    }
};

struct D_HASH {
    const int B1 = 256;
    const int B2 = 128;
    const int M1 = 1e9 + 7;
    const int M2 = 1e9 + 9;

    array<HASH , 2> h;
    D_HASH() : h{HASH(M1 , B1) , HASH(M2 , B2)} {}

    D_HASH(string str) : h{HASH(M1, B1), HASH(M2, B2)} {
        for (char c : str) {
            push_back(c);
        }
    }

    void push_back(int x) { // x != 0
        h[0].push_back(x);
        h[1].push_back(x);
    }

    array<int , 2> get(int l , int r) { // send zero based
        assert(l <= r);
        return {h[0].get(l , r) , h[1].get(l , r)};
    };
};

string rev (string s) {
    string t = s;
    reverse(t.begin() , t.end());
    return t;
}

enum {odd , even};

const int N = 1e5 + 5;
int first[N][2] , second[N][2];
long long New[N][26];
long long sub[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    string str;
    cin >> str;

    int n = str.size();
    D_HASH h(str) , rh(rev(str));

    auto same = [&](int l , int r , int s , int e) {
        if (l < 0 || e >= n)
            return false;
        return h.get(l , r) == rh.get(n - e - 1, n - s - 1); // reverse one
    };

    for (int i = 0 ;i < n ;i++) {
        int l = 1 , r = n;
        // even
        while (l <= r) {
            int mid = (l + r) / 2;
            if (same(i - mid , i - 1 , i , i + mid - 1)) {
                first[i][even] = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }


        int e = i - first[i][even] - 2;
        int s = i + first[i][even] + 1;

        l = 1 , r = n;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (same(e - mid + 1 , e , s , s + mid - 1)) {
                second[i][even] = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        // odd
        l = 1 , r = n;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (same(i - mid + 1 , i , i , i + mid - 1)) {
                first[i][odd] = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        e = i - first[i][odd] - 1 , s = i + first[i][odd] + 1;
        l = 1 , r = n;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (same(e - mid + 1 , e , s , s + mid - 1)) {
                second[i][odd] = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        int t = i - first[i][even] - 1 , tt = i + first[i][even];
        if (t > 0 && tt < n) {
            New[tt][str[t] - 'a'] += second[i][even] + 1;
            New[t][str[tt] - 'a'] += second[i][even] + 1;
        }

        t = i - first[i][odd] , tt = i + first[i][odd];
        if (t > 0 && tt < n) {
            New[tt][str[t] - 'a'] += second[i][odd] + 1;
            New[t][str[tt] - 'a'] += second[i][odd] + 1;
        }
    }


    int active = 0;
    long long pal = 0;
    vector<int> en(n);
    for (int i = 0 ;i < n ;i++) {
        if (first[i][even]) {
            active++;
            pal += first[i][even];
            en[i + first[i][even] - 1]++;
        }
        sub[i] += pal;
        active++;
        pal += first[i][odd];
        en[i + first[i][odd] - 1]++;
        pal -= active;
        active -= en[i];
    }

    active = 0 , pal = 0;
    fill(en.begin() , en.end() , 0);

    for (int i = n - 1 ;i >= 0 ;i--) {
        sub[i] += pal;
        active++;
        pal += first[i][odd];
        en[i - first[i][odd] + 1]++;
        pal -= active;
        active -= en[i];
        if (first[i][even]) {
            active++;
            pal += first[i][even];
            en[i - first[i][even]]++;
        }
    }


    long long pals = 0 , mx = 0;
    for (int i = 0 ;i < n ;i++) {
        pals += first[i][odd] + first[i][even];
        for (int j = 0 ;j < 26 ;j++)
            mx = max(mx , New[i][j] - sub[i]);
    }

    cout << pals + mx;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from palinilap.cpp:5:
palinilap.cpp: In member function 'int HASH::get(int, int)':
palinilap.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         assert(r + 1 < hashes.size());
      |                ~~~~~~^~~~~~~~~~~~~~~

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