oj.uz

Submission #1053981

# Submission time Handle Problem Language Result Execution time Memory
1053981 2024-08-12T01:51:45 Z 1bin Palindromes (APIO14_palindrome) C++17
100 / 100
 146 ms 74652 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 0 ms 2432 KB Output is correct
23 Correct 0 ms 2396 KB Output is correct
24 Correct 0 ms 2396 KB Output is correct
25 Correct 0 ms 2648 KB Output is correct
26 Correct 0 ms 2396 KB Output is correct
27 Correct 0 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 0 ms 2396 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct
31 Correct 0 ms 2516 KB Output is correct
32 Correct 0 ms 2396 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2516 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 0 ms 2652 KB Output is correct
12 Correct 1 ms 2520 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3672 KB Output is correct
2 Correct 3 ms 3708 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 3 ms 3932 KB Output is correct
7 Correct 3 ms 3676 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 3 ms 3932 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16936 KB Output is correct
2 Correct 24 ms 16936 KB Output is correct
3 Correct 46 ms 26408 KB Output is correct
4 Correct 39 ms 26364 KB Output is correct
5 Correct 26 ms 16924 KB Output is correct
6 Correct 26 ms 16936 KB Output is correct
7 Correct 32 ms 21544 KB Output is correct
8 Correct 26 ms 17700 KB Output is correct
9 Correct 28 ms 19232 KB Output is correct
10 Correct 35 ms 19996 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 46908 KB Output is correct
2 Correct 78 ms 46488 KB Output is correct
3 Correct 146 ms 74648 KB Output is correct
4 Correct 127 ms 74652 KB Output is correct
5 Correct 87 ms 46744 KB Output is correct
6 Correct 95 ms 54424 KB Output is correct
7 Correct 106 ms 59292 KB Output is correct
8 Correct 84 ms 47772 KB Output is correct
9 Correct 76 ms 47768 KB Output is correct
10 Correct 102 ms 56008 KB Output is correct
11 Correct 80 ms 46488 KB Output is correct
12 Correct 81 ms 50228 KB Output is correct