Submission #1053981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053981		1bin	Palindromes (APIO14_palindrome)	C++17	100 / 100	146 ms	74652 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const ll M1 = 1e9 + 7, M2 = 1e9 + 9;
const int LM = 6e5 + 5;
ll n, r[LM], e, x, ans;
string s, t;
ll X1, X2, H[LM][2], pw[LM][2];
struct node{
    ll len, l, r, cnt;
    pair<ll, ll> h;
    bool operator<(const node & x)const{
        if(len == x.len) return h < x.h;
        return len > x.len;
    }  
};
multiset<node> ms;
// len hash1 hash2 l r cnt

pair<ll, ll> Hash(int l, int r){
    ll y1 = ((H[l][0] - H[r + 1][0] * pw[r - l + 1][0]) % M1 + M1) % M1;
    ll y2 = ((H[l][1] - H[r + 1][1] * pw[r - l + 1][1]) % M2 + M2) % M2;
    return {y1, y2};
}

void get_hash(string& s){
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int n = s.size();
    static uniform_int_distribution<int> f(300, M1 - 1);
    X1 = f(rng); X2 = f(rng);

    pw[0][0] = pw[0][1] = 1;
    for(int i = 1; i <= n; i++){
        pw[i][0] = pw[i - 1][0] * X1 % M1;
        pw[i][1] = pw[i - 1][1] * X2 % M2;
    }

    for(int i = n - 1; i >= 0; i--){
        H[i][0] = (H[i + 1][0] * X1 + s[i]) % M1;
        H[i][1] = (H[i + 1][1] * X2 + s[i]) % M2;
    }
    return;
}

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

    cin >> t;
    get_hash(t);
    s += '#';
    for(int i = 0; i < t.size(); i++) s += t[i], s += '#';
    n = s.size();
    for(int i = 0; i < n; i++){
        if(i <= e) r[i] = min(r[2 * x - i], e - i);
        while(i - r[i] - 1 >= 0 && i + r[i] + 1 < n && s[i - r[i] - 1] == s[i + r[i] + 1]) r[i]++;
        if(i + r[i] > e){
            e = i + r[i]; x = i;
        }
    }
    for(int i = 0; i < n; i++){
        int s, e = -1, m = i / 2;
        if(i & 1) s = m - r[i]/2, e = m + r[i]/2;
        else if(r[i]) s = m - r[i]/2, e = s + r[i] - 1;
        if(e != -1) ms.insert({r[i], s, e, 1, Hash(s, e)});
    }
    while(ms.size()){
        auto cur = *ms.begin(); ms.erase(ms.begin());
        while(ms.size() && cur.h == ms.begin()->h){
            cur.cnt += ms.begin()->cnt;
            ms.erase(ms.begin());
        }
        ans = max(ans, cur.len * cur.cnt);
        cur.l++; cur.r--;
        if(cur.l <= cur.r){
            cur.len -= 2;
            cur.h = Hash(cur.l, cur.r);
            ms.emplace(cur);
        }
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 0; i < t.size(); i++) s += t[i], s += '#';
      |                    ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27