답안 #337462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
337462 2020-12-20T22:15:32 Z wolf Palinilap (COI16_palinilap) C++14
100 / 100
394 ms 27360 KB
#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

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());
      |                ~~~~~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1772 KB Output is correct
2 Correct 9 ms 1772 KB Output is correct
3 Correct 14 ms 1772 KB Output is correct
4 Correct 8 ms 1248 KB Output is correct
5 Correct 12 ms 1516 KB Output is correct
6 Correct 14 ms 1772 KB Output is correct
7 Correct 14 ms 1772 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 392 ms 27256 KB Output is correct
2 Correct 203 ms 26464 KB Output is correct
3 Correct 218 ms 26464 KB Output is correct
4 Correct 377 ms 27360 KB Output is correct
5 Correct 380 ms 27232 KB Output is correct
6 Correct 375 ms 27232 KB Output is correct
7 Correct 380 ms 27232 KB Output is correct
8 Correct 121 ms 6112 KB Output is correct
9 Correct 380 ms 27232 KB Output is correct
10 Correct 380 ms 27360 KB Output is correct
11 Correct 200 ms 26812 KB Output is correct
12 Correct 379 ms 27232 KB Output is correct
13 Correct 358 ms 27232 KB Output is correct
14 Correct 379 ms 27360 KB Output is correct
15 Correct 394 ms 27232 KB Output is correct
16 Correct 245 ms 26848 KB Output is correct
17 Correct 369 ms 27232 KB Output is correct
18 Correct 393 ms 27232 KB Output is correct
19 Correct 377 ms 27232 KB Output is correct