oj.uz

Submission #542156

# Submission time Handle Problem Language Result Execution time Memory
542156 2022-03-25T14:51:25 Z Olympia Palindromes (APIO14_palindrome) C++17
100 / 100
 837 ms 50960 KB 
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
 
int64_t binPow (int64_t x, int64_t y, int64_t MOD) {
    x %= MOD;
    int64_t res = x;
    int64_t ans = 1;
    while (y > 0) {
        if (y & 1) {
            ans *= res, ans %= MOD;
        }
        res *= res, res %= MOD;
        y /= 2;
    }
    return ans;
}
int64_t inv (int64_t x, int64_t MOD) {
    return binPow(x, MOD - 2, MOD);
}
vector<int64_t> powr = {1};
vector<int64_t> ipowr = {1};
struct Hasher {
    void resz (int mod, int base, string str) {
        int n = str.size();
        this->sz = n;
        this->MOD = mod, this->BASE = base;
        this->pref.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            pref[i] = (pref[i - 1] + (powr[n - i] * (str[i - 1] - 'a' + 1)) % MOD) % MOD;
            pref[i] %= MOD;
        }
    }
    int sz;
    int MOD;
    int BASE;
    vector<int64_t> pref;
    int64_t query (int l, int r) {
        if (l > sz || r > sz || l > r || l < 0 || r < 0) return -1;
        return (ipowr[sz - r - 1] * (pref[r + 1] - pref[l] + MOD) % MOD) % MOD;
    }
};
Hasher h1;
Hasher h2;
string s1;
bool isPalindrome (int l, int r) {
    if (l < 0 || r >= s1.length()) return false;
    return (h1.query(l, r) == h2.query((int)s1.length() - r - 1, (int)s1.length() - l - 1));
}
vector<int> suffix_array(string S) {
    int N = S.size();
    vector<int> sa(N), classes(N);
    for (int i = 0; i < N; i++) {
        sa[i] = N - 1 - i;
        classes[i] = S[i];
    }
    stable_sort(sa.begin(), sa.end(), [&S](int i, int j) {
        return S[i] < S[j];
    });
    for (int len = 1; len < N; len *= 2) {
        vector<int> c(classes);
        for (int i = 0; i < N; i++) {
            bool same = i && sa[i - 1] + len < N
                        && c[sa[i]] == c[sa[i - 1]]
                        && c[sa[i] + len / 2] == c[sa[i - 1] + len / 2];
            classes[sa[i]] = same ? classes[sa[i - 1]] : i;
        }
        vector<int> cnt(N), s(sa);
        for (int i = 0; i < N; i++)
            cnt[i] = i;
        for (int i = 0; i < N; i++) {
            int s1 = s[i] - len;
            if (s1 >= 0)
                sa[cnt[classes[s1]]++] = s1;
        }
    }
    return sa;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    while (powr.size() != 1e6 + 5) {
        powr.push_back(powr.back() * 31);
        powr.back() %= (int)1e9 + 9;
    }
    ipowr.resize(powr.size());
    ipowr[0] = 1; ipowr[1] = inv(powr[1], 1e9 + 9);
    for (int i = 2; i < powr.size(); i++) {
        ipowr[i] = (ipowr[i - 1] * ipowr[1]) % ((int)1e9 + 9);
    }
    cin >> s1;
    h1.resz((int)1e9 + 9, 31, s1);
    reverse(s1.begin(), s1.end());
    h2.resz((int)1e9 + 9, 31, s1);
    reverse(s1.begin(), s1.end());
    vector<pair<int,int>> vec;
    for (int i = 0;  i < s1.size(); i++) {
        int l = 0;
        int r = s1.length();
        while (l != r) {
            //cout << l << " " << r << '\n';
            int m = (l + r + 1)/2;
            if (isPalindrome(i - m, i + m)) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        vec.emplace_back(i - l, i + l);
        //[...aa...]
        if (i == s1.length() || s1[i] != s1[i + 1]) {
            continue;
        }
        l = 0;
        r = s1.length();
        while (l != r) {
            int m = (l + r + 1)/2;
            if (isPalindrome(i - m, i + m + 1)) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        vec.emplace_back(i - l, i + l + 1);
        //cout << i << " " << l << '\n';
    }
    map<int64_t,pair<int,int>> myMap;
    for (auto& p: vec) {
        pair<int,int> q = p;
        while (q.first <= q.second) {
            if (myMap.count(h1.query(q.first, q.second))) {
                break;
            }
            myMap[h1.query(q.first, q.second)] = q;
            q.first++, q.second--;
        }
    }
    vector<int> v = suffix_array(s1);
    vector<int> id(v.size() + 1);
    for (int i = 0; i < v.size(); i++) {
        id[v[i]] = i;
    }
    int64_t ans = 0;
    for (auto& p: myMap) {
        int tot = h1.query(p.second.first, p.second.second);
        int l = 0;
        int r = id[p.second.first];
        while (l != r) {
            int m = (l + r)/2;
            if (h1.query(v[m], v[m] + p.second.second - p.second.first) == tot) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        int L = l;
        l = id[p.second.first];
        r = s1.length() - 1;
        while (l != r) {
            int m = (l + r + 1)/2;
            if (h1.query(v[m], v[m] + p.second.second - p.second.first) == tot) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        if (p.second.first - p.second.second == 2 && l - L + 1 == 10) {
            cout << p.second.first << " " << p.second.second << " " << l - L + 1 << '\n';
        }
        ans = max(ans, (int64_t)(p.second.second - p.second.first + 1) * (l - L + 1));
    }
    cout << ans;
}

Compilation message

palindrome.cpp:14: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   14 | #pragma GCC optimization ("O3")
      | 
palindrome.cpp:15: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   15 | #pragma GCC optimization ("unroll-loops")
      | 
palindrome.cpp: In function 'bool isPalindrome(int, int)':
palindrome.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     if (l < 0 || r >= s1.length()) return false;
      |                  ~~^~~~~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 2; i < powr.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
palindrome.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0;  i < s1.size(); i++) {
      |                      ~~^~~~~~~~~~~
palindrome.cpp:124:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         if (i == s1.length() || s1[i] != s1[i + 1]) {
      |             ~~^~~~~~~~~~~~~~
palindrome.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16108 KB Output is correct
2 Correct 25 ms 16140 KB Output is correct
3 Correct 25 ms 16116 KB Output is correct
4 Correct 25 ms 16076 KB Output is correct
5 Correct 24 ms 16104 KB Output is correct
6 Correct 24 ms 16068 KB Output is correct
7 Correct 23 ms 16140 KB Output is correct
8 Correct 25 ms 16068 KB Output is correct
9 Correct 24 ms 16048 KB Output is correct
10 Correct 24 ms 16128 KB Output is correct
11 Correct 23 ms 16084 KB Output is correct
12 Correct 22 ms 16088 KB Output is correct
13 Correct 24 ms 16072 KB Output is correct
14 Correct 23 ms 16068 KB Output is correct
15 Correct 24 ms 16044 KB Output is correct
16 Correct 24 ms 16068 KB Output is correct
17 Correct 24 ms 16124 KB Output is correct
18 Correct 23 ms 16068 KB Output is correct
19 Correct 25 ms 16056 KB Output is correct
20 Correct 24 ms 16060 KB Output is correct
21 Correct 24 ms 16068 KB Output is correct
22 Correct 25 ms 16028 KB Output is correct
23 Correct 24 ms 16068 KB Output is correct
24 Correct 24 ms 16120 KB Output is correct
25 Correct 23 ms 16136 KB Output is correct
26 Correct 24 ms 16068 KB Output is correct
27 Correct 24 ms 16196 KB Output is correct
28 Correct 26 ms 16036 KB Output is correct
29 Correct 26 ms 16124 KB Output is correct
30 Correct 25 ms 16116 KB Output is correct
31 Correct 26 ms 16100 KB Output is correct
32 Correct 25 ms 16136 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16068 KB Output is correct
2 Correct 27 ms 16120 KB Output is correct
3 Correct 24 ms 16132 KB Output is correct
4 Correct 25 ms 16012 KB Output is correct
5 Correct 27 ms 16020 KB Output is correct
6 Correct 25 ms 16140 KB Output is correct
7 Correct 24 ms 16052 KB Output is correct
8 Correct 26 ms 16032 KB Output is correct
9 Correct 26 ms 16108 KB Output is correct
10 Correct 25 ms 16108 KB Output is correct
11 Correct 24 ms 16112 KB Output is correct
12 Correct 24 ms 16068 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17084 KB Output is correct
2 Correct 34 ms 17068 KB Output is correct
3 Correct 37 ms 17068 KB Output is correct
4 Correct 37 ms 17036 KB Output is correct
5 Correct 37 ms 17020 KB Output is correct
6 Correct 37 ms 17028 KB Output is correct
7 Correct 36 ms 17100 KB Output is correct
8 Correct 30 ms 16372 KB Output is correct
9 Correct 29 ms 16452 KB Output is correct
10 Correct 33 ms 16836 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 26720 KB Output is correct
2 Correct 193 ms 26736 KB Output is correct
3 Correct 195 ms 27512 KB Output is correct
4 Correct 232 ms 27524 KB Output is correct
5 Correct 147 ms 24464 KB Output is correct
6 Correct 160 ms 25028 KB Output is correct
7 Correct 203 ms 26100 KB Output is correct
8 Correct 118 ms 20728 KB Output is correct
9 Correct 131 ms 22164 KB Output is correct
10 Correct 152 ms 24200 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 48180 KB Output is correct
2 Correct 742 ms 48520 KB Output is correct
3 Correct 748 ms 50960 KB Output is correct
4 Correct 837 ms 50916 KB Output is correct
5 Correct 415 ms 36780 KB Output is correct
6 Correct 722 ms 46336 KB Output is correct
7 Correct 691 ms 45044 KB Output is correct
8 Correct 358 ms 30456 KB Output is correct
9 Correct 376 ms 30380 KB Output is correct
10 Correct 479 ms 37372 KB Output is correct
11 Correct 633 ms 48600 KB Output is correct
12 Correct 384 ms 32940 KB Output is correct