oj.uz

Submission #564964

# Submission time Handle Problem Language Result Execution time Memory
564964 2022-05-20T05:31:59 Z ac2hu Palindromes (APIO14_palindrome) C++14
47 / 100
 878 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
 
// Generate random base in (before, after) open interval:
int gen_base(const int before, const int after) {
    auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    std::mt19937 mt_rand(seed);
    int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
    return base % 2 == 0 ? base-1 : base;
}
 
struct PolyHash {/*{{{*/
    // -------- Static variables --------
    static const int mod = (int)1e9+123; // prime mod of polynomial hashing
    static std::vector<int> pow1;        // powers of base modulo mod
    static std::vector<ull> pow2;        // powers of base modulo 2^64
    static int base;                     // base (point of hashing)
 
    // --------- Static functons --------
    static inline int diff(int a, int b) { 
    	// Diff between `a` and `b` modulo mod (0 <= a < mod, 0 <= b < mod)
        return (a -= b) < 0 ? a + mod : a;
    }
 
    // -------------- Variables of class -------------
    std::vector<int> pref1; // Hash on prefix modulo mod
    std::vector<ull> pref2; // Hash on prefix modulo 2^64
 
    // Cunstructor from string:
    PolyHash(const std::string& s)
        : pref1(s.size()+1u, 0)
        , pref2(s.size()+1u, 0)
    {
        assert(base < mod);
        const int n = s.size(); // Firstly calculated needed power of base:
        while ((int)pow1.size() <= n) {
            pow1.push_back(1LL * pow1.back() * base % mod);
            pow2.push_back(pow2.back() * base);
        }
        for (int i = 0; i < n; ++i) { // Fill arrays with polynomial hashes on prefix
            assert(base > s[i]);
            pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
            pref2[i+1] = pref2[i] + s[i] * pow2[i];
        }
    }
 
    // Polynomial hash of subsequence [pos, pos+len)
    // If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
    inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
        int hash1 = pref1[pos+len] - pref1[pos];
        ull hash2 = pref2[pos+len] - pref2[pos];
        if (hash1 < 0) hash1 += mod;
        if (mxPow != 0) {
            hash1 = 1LL * hash1 * pow1[mxPow-(pos+len-1)] % mod;
            hash2 *= pow2[mxPow-(pos+len-1)];
        }
        return std::make_pair(hash1, hash2);
    }
};/*}}}*/
int PolyHash::base((int)1e9 + 7);
vector<int> PolyHash::pow1{1};
vector<ull> PolyHash::pow2{1};

int brute(string s){
    // O(n^2) is easy 
    // Find all palindromes and put it in a map and then itterate to find maximum
    int n = s.size();
    vector<vector<bool>> is_pali(n, vector<bool>(n));
    for(int siz = 0;siz<n;siz++){
        for(int i = 0;i + siz<n;i++){
            int j = i + siz;
            if(siz == 0)is_pali[i][j] = true;
            else if(siz == 1)is_pali[i][j] = (s[i] == s[j]);
            else is_pali[i][j] = ((s[i] == s[j])&&is_pali[i + 1][j - 1]);
        }
    }
    vector<vector<bool>> sel(n, vector<bool>(n, false));
    PolyHash hs(s);
    int ans = 0;
    auto count = [&](pair<int,ull> hval, int sz){
        int c = 0;
        for(int i = 0;i<n;i++){
            int j = i + sz;
            if(j > n - 1)break;
            if(hval == hs(i, sz + 1, n)){
                sel[i][j] = true;
                c++;
            }
        }
        return c;
    };
    for(int siz = 0;siz<n;siz++){
        for(int i = 0;i+siz<n;i++){
            int j = i + siz;
            if(!sel[i][j] && is_pali[i][j]){
                int c = count(hs(i, siz + 1,n), siz);
                ans = max(ans, c*(siz + 1));
            }
        }
    }
    return ans;
}
signed main(){
    string s;cin >> s;
    cout << brute(s) << "\n";
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 6 ms 696 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 5 ms 612 KB Output is correct
6 Correct 7 ms 696 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 6 ms 684 KB Output is correct
9 Correct 7 ms 596 KB Output is correct
10 Correct 4 ms 684 KB Output is correct
11 Correct 5 ms 596 KB Output is correct
12 Correct 8 ms 596 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 878 ms 26272 KB Output is correct
2 Correct 837 ms 26244 KB Output is correct
3 Correct 746 ms 26236 KB Output is correct
4 Correct 826 ms 26268 KB Output is correct
5 Correct 815 ms 26236 KB Output is correct
6 Correct 791 ms 26232 KB Output is correct
7 Correct 863 ms 26244 KB Output is correct
8 Correct 547 ms 26220 KB Output is correct
9 Correct 605 ms 26236 KB Output is correct
10 Correct 806 ms 26236 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -