oj.uz

Submission #562884

# Submission time Handle Problem Language Result Execution time Memory
562884 2022-05-15T13:15:48 Z beep_boop Palindromes (APIO14_palindrome) C++17
23 / 100
 1000 ms 20328 KB 
/*
 * Created at 5:39 PM on 15 May, 2022
 */

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <numeric>
#include <cassert>
#include <functional>

using namespace std;

#define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
#define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SZ(x) (int)(x).size()
#define vt vector
#define trav(a, x) for(auto& (a): (x))
#define DO if(true)

#define mp make_pair
#define pb push_back
#define eb emplace_back

//#define int int64_t

typedef vector<int> vi;
typedef pair<int, int> pi;

#define mod 1000000007

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

template<typename T>
void read(vector<T> &a, int n) {
    a.resize(n);
    for (auto &x: a) cin >> x;
}

template<class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &v) {
    out << "(";
    out << v.first << ", " << v.second;
    return out << ")";
}

template<class T>
ostream &operator<<(ostream &out, const vector<T> &v) {
    out << "[";
    list(i, SZ(v)) {
        if (i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

template<typename T>
void print(vector<T> &a) {
    for (const auto &x: a) cout << x << ' ';
    cout << '\n';
}

template<typename T>
void MOD(T &x, int m = mod) {
    x %= m;
    if (x < 0) x += m;
}

#define trace(...) dbg(#__VA_ARGS__, __VA_ARGS__)

template<typename T>
void dbg(const char *name, T &&arg1) {
    cout << name << " : " << arg1 << '\n';
}

template<typename T, typename... U>
void dbg(const char *names, T &&arg1, U &&... args) {
    const char *comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | ";
    dbg(comma + 1, args...);
}

template<class T>
void read(T &x) {
    cin >> x;
}

template<class T, class... U>
void read(T &t, U &... u) {
    read(t);
    read(u...);
}

int gcd(int a, int b) { return !a ? b : gcd(b % a, a); }

int ceil_div(int a, int b) { return (a + b - 1) / b; }

using ll = long long;

//Rolling Hash for Strings
struct StringHash {
    int n = 1;
    string s;

    //The Hashes
    const ll A = 911382323;
    const ll M[2] = {999999937, 10620793};

    vt<ll> pow[2], pref[2];

    void init(const string &x) {
        s = x;
        n = SZ(s);

        //Computing the powers of the primes
        list(k, 2) {
            pow[k].resize(n + 1);
            pow[k][0] = 1;
            rep(i, 1, n + 1) {
                pow[k][i] = A * pow[k][i - 1];
                MOD(pow[k][i], M[k]);
            }
        }

        //Computing the prefix sums
        list(k, 2) {
            pref[k].resize(n + 1, 0);
            pref[k][1] = s[0] - 'a';
            rep(i, 2, n + 1) {
                pref[k][i] = pref[k][i - 1] * A + (s[i - 1] - 'a');
                MOD(pref[k][i], M[k]);
            }
        }
    }

    //returns the hash of [l, r)
    vt<ll> get(int l, int r) {
        vt<ll> res(2);
        list(k, 2) {
            res[k] = pref[k][r] - (pref[k][l] * pow[k][r - l]);
            MOD(res[k], M[k]);
        }
        return res;
    }

    //Checks if [l, r) is equal to [x, y)
    bool equal(int l, int r, int x, int y) {
        return get(l, r) == get(x, y);
    }
};

const int N = 1002;
int n;
string s;

int32_t main() {
    setIO();

    read(s);
    n = SZ(s);

    string t = s;
    reverse(ALL(t));

    StringHash st;
    st.init(s);

    StringHash ts;
    ts.init(t);

    ll ans = 0;

    rep(len, 1, n + 1){
        map<vt<ll>, int> cnt;
        list(i, n - len + 1){
//            if(len == 1) {
//                trace(i, st.get(i, i + len), ts.get(n - i - 1 - len, n - i - 1));
//            }
            if(st.get(i, i + len) == ts.get(n - i - len, n - i)){
                cnt[st.get(i, i + len)]++;
            }
        }

        trav(c, cnt){
            ans = max(ans, len * 1LL * c.second);
        }
    }

    cout << ans << '\n';
    return 0;
}

Compilation message

palindrome.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<T>&)':
palindrome.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
palindrome.cpp:63:5: note: in expansion of macro 'list'
   63 |     list(i, SZ(v)) {
      |     ^~~~
palindrome.cpp: In member function 'void StringHash::init(const string&)':
palindrome.cpp:23:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
palindrome.cpp:129:9: note: in expansion of macro 'list'
  129 |         list(k, 2) {
      |         ^~~~
palindrome.cpp:22:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
      |                               ^
palindrome.cpp:132:13: note: in expansion of macro 'rep'
  132 |             rep(i, 1, n + 1) {
      |             ^~~
palindrome.cpp:23:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
palindrome.cpp:139:9: note: in expansion of macro 'list'
  139 |         list(k, 2) {
      |         ^~~~
palindrome.cpp:22:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
      |                               ^
palindrome.cpp:142:13: note: in expansion of macro 'rep'
  142 |             rep(i, 2, n + 1) {
      |             ^~~
palindrome.cpp: In member function 'std::vector<long long int> StringHash::get(int, int)':
palindrome.cpp:23:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
palindrome.cpp:152:9: note: in expansion of macro 'list'
  152 |         list(k, 2) {
      |         ^~~~
palindrome.cpp: In function 'int32_t main()':
palindrome.cpp:22:31: warning: unnecessary parentheses in declaration of 'len' [-Wparentheses]
   22 | #define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
      |                               ^
palindrome.cpp:186:5: note: in expansion of macro 'rep'
  186 |     rep(len, 1, n + 1){
      |     ^~~
palindrome.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
palindrome.cpp:188:9: note: in expansion of macro 'list'
  188 |         list(i, n - len + 1){
      |         ^~~~
palindrome.cpp:28:30: warning: unnecessary parentheses in declaration of 'c' [-Wparentheses]
   28 | #define trav(a, x) for(auto& (a): (x))
      |                              ^
palindrome.cpp:197:9: note: in expansion of macro 'trav'
  197 |         trav(c, cnt){
      |         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 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 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 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 292 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 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 2 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 324 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 316 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 40 ms 340 KB Output is correct
2 Correct 35 ms 380 KB Output is correct
3 Correct 62 ms 340 KB Output is correct
4 Correct 33 ms 372 KB Output is correct
5 Correct 46 ms 368 KB Output is correct
6 Correct 46 ms 340 KB Output is correct
7 Correct 28 ms 340 KB Output is correct
8 Correct 38 ms 368 KB Output is correct
9 Correct 29 ms 340 KB Output is correct
10 Correct 30 ms 372 KB Output is correct
11 Correct 29 ms 340 KB Output is correct
12 Correct 31 ms 340 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 6996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 20328 KB Time limit exceeded
2 Halted 0 ms 0 KB -