제출 #562874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
562874		beep_boop	수열 (APIO14_sequence)	C++14	0 / 100	1 ms	424 KiB

sequence

/*
 * 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(st.get(i, i + len) == ts.get(i, i + len)){
                cnt[st.get(i, i + len)]++;
            }
        }

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

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

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29