oj.uz

Submission #887832

# Submission time Handle Problem Language Result Execution time Memory
887832 2023-12-15T09:41:16 Z phong Palindromes (APIO14_palindrome) C++17
100 / 100
 707 ms 72960 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 3e5 + 5;
const ll oo = 1e18;
const int lg = 18;
const int tx = 2;
const ll base = 311;
#define pii pair<int, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;

ll mod[] = {(int)1e9 + 7, (int)1e9 + 9};
int n, cur = 0;
string s;
ll pw[2][nmax], h[nmax][2];
int D_odd[nmax];
int D_even[nmax];

void Calc_D_odd() {
    int L = 1;
    int R = 0;
    for(int i = 1 ; i <= n; i++) {
        if(i > R) D_odd[i] = 0;
        else D_odd[i] = min(R - i, D_odd[L + (R - i)]);
        while(i - D_odd[i] - 1 > 0 && i + D_odd[i] + 1 <= n && s[i - D_odd[i] - 1] == s[i + D_odd[i] + 1]) {
            D_odd[i]++;
        }

        if(i + D_odd[i] > R) {
            R = i + D_odd[i];
            L = i - D_odd[i];
        }
    }
}

void Calc_D_even() {
    int L = 1;
    int R = 0;
    for(int i = 1 ; i < n; i++) {
        int j = i + 1;
        if(j > R) D_even[i] = 0;
        else D_even[i] = min(R - j + 1, D_even[L + (R - j)]);
        while(i - D_even[i] > 0 && j + D_even[i] <= n && s[i - D_even[i]] == s[j + D_even[i]]) {
            D_even[i]++;
        }
        if(i + D_even[i] > R) {
            R = i + D_even[i];
            L = j - D_even[i];
        }
    }
}


void Init(){
    for(int j = 0; j < tx; ++j) pw[j][0] = 1;
    for(int i = 1, j; i <= n; ++i){
        for(int j = 0; j < tx; ++j){
            pw[j][i] = pw[j][i - 1] * base % mod[j];
            h[i][j] = (h[i - 1][j] * base + s[i] - 'a' + 1) % mod[j];
        }
    }
}
ll get(int l, int r, int ix){
    return (h[r][ix] - h[l - 1][ix] * pw[ix][r - l + 1] + mod[ix] * mod[ix]) % mod[ix];
}

map<pii, bool> mp;
map<pii, int>  ind;
int cnt[nmax], f[nmax];
vector<int> tmp;
vector<int> adj[nmax];

void update(int l, int r){
    bool ok = 1;
    while(l <= r){
        pii x = {get(l, r, 0), get(l, r, 1)};
        if(!mp[x]){
            ind[x] = ++cur;
            tmp.push_back(cur);
            if(ok){
                f[cur]++;
                ok = 0;
            }
            cnt[cur] = r - l + 1;
            mp[x] = 1;
        }
        else{
            int id = ind[x];
            tmp.push_back(id);
            if(ok) f[id]++;

            break;
        }
        ++l, --r;
    }
    if(l > r) tmp.push_back(0);
    int x = (int)tmp.size() - 1;
    for(int i = 0; i < x; ++i){
        int x = tmp[i], y = tmp[i + 1];
        adj[y].push_back(x);
    }
    tmp.clear();
}
void dfs(int u){
    for(auto v : adj[u]){
        dfs(v);
        f[u] += f[v];
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> s;
    n = s.size(); s = ' ' + s + ' ';
    Init();
    Calc_D_odd();
    Calc_D_even();
    for(int i = 1; i <= n; ++i){
        update(i - D_odd[i], i + D_odd[i]);
        if(i < n) update(i - D_even[i] + 1, i + D_even[i]);
    }
    dfs(0);

    ll ans = 0;
    for(int i = 1; i <= cur; ++i){
        ans = max(ans, 1ll * f[i] * cnt[i]);
    }
    cout << ans;
}
/*

*/

Compilation message

palindrome.cpp: In function 'void Init()':
palindrome.cpp:62:20: warning: unused variable 'j' [-Wunused-variable]
   62 |     for(int i = 1, j; i <= n; ++i){
      |                    ^
palindrome.cpp: At global scope:
palindrome.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main(){
      | ^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 15196 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14936 KB Output is correct
10 Correct 2 ms 14940 KB Output is correct
11 Correct 3 ms 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16928 KB Output is correct
2 Correct 10 ms 16812 KB Output is correct
3 Correct 12 ms 16728 KB Output is correct
4 Correct 12 ms 16876 KB Output is correct
5 Correct 9 ms 16712 KB Output is correct
6 Correct 9 ms 16732 KB Output is correct
7 Correct 10 ms 16572 KB Output is correct
8 Correct 3 ms 15192 KB Output is correct
9 Correct 4 ms 15196 KB Output is correct
10 Correct 7 ms 16140 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 37124 KB Output is correct
2 Correct 125 ms 36636 KB Output is correct
3 Correct 159 ms 37148 KB Output is correct
4 Correct 147 ms 36600 KB Output is correct
5 Correct 93 ms 36972 KB Output is correct
6 Correct 75 ms 31992 KB Output is correct
7 Correct 112 ms 33632 KB Output is correct
8 Correct 13 ms 20476 KB Output is correct
9 Correct 35 ms 24060 KB Output is correct
10 Correct 84 ms 34296 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 72908 KB Output is correct
2 Correct 598 ms 70220 KB Output is correct
3 Correct 707 ms 72956 KB Output is correct
4 Correct 648 ms 70420 KB Output is correct
5 Correct 377 ms 72960 KB Output is correct
6 Correct 451 ms 64648 KB Output is correct
7 Correct 439 ms 61948 KB Output is correct
8 Correct 35 ms 22164 KB Output is correct
9 Correct 36 ms 22336 KB Output is correct
10 Correct 318 ms 64384 KB Output is correct
11 Correct 475 ms 72852 KB Output is correct
12 Correct 65 ms 27012 KB Output is correct