제출 #555043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555043		MrDeboo	회문 (APIO14_palindrome)	C++17	23 / 100	1093 ms	14064 KiB

palindrome

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<int MOD>
struct ModInt {
    unsigned x;
    ModInt() : x(0) { }
    ModInt(signed sig) : x(sig%MOD) {  }
    ModInt(signed long long sig) : x(sig%MOD) { }
    int get() const { return (int)x; }
    ModInt pow(long long p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }

    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); }

    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    bool operator<(ModInt that) const { return x < that.x; }
    friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
};

#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
#define fs first
#define sc second
#define unique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
#define endl '\n'
#define sz(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef long double ld;
typedef ModInt<1000000007> mint;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;

const int mxn=200000;
// const ll mod=1000000007;
const ll INF=1000000000000000000;

template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.fs;
	return cin >> p.sc;
}

#define MAXLEN 1000010

constexpr uint64_t mod = (1ULL << 61) - 1;

const uint64_t seed = chrono::system_clock::now().time_since_epoch().count();
const uint64_t base = mt19937_64(seed)() % (mod / 3) + (mod / 3);

uint64_t base_pow[MAXLEN];

int64_t modmul(uint64_t a, uint64_t b){
    uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
    uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
    uint64_t ret = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
    ret = (ret & mod) + (ret >> 61);
    ret = (ret & mod) + (ret >> 61);
    return ret - 1;
}

void init(){
    base_pow[0] = 1;
    for (int i = 1; i < MAXLEN; i++){
        base_pow[i] = modmul(base_pow[i - 1], base);
    }
}


struct PolyHash{
    /// Remove suff vector and usage if reverse hash is not required for more speed
    vector<int64_t> pref, suff;

    PolyHash() {}

    template <typename T>
    PolyHash(const vector<T>& ar){
        if (!base_pow[0]) init();

        int n = ar.size();
        assert(n < MAXLEN);
        pref.resize(n + 3, 0), suff.resize(n + 3, 0);

        for (int i = 1; i <= n; i++){
            pref[i] = modmul(pref[i - 1], base) + ar[i - 1] + 997;
            if (pref[i] >= mod) pref[i] -= mod;
        }

        for (int i = n; i >= 1; i--){
            suff[i] = modmul(suff[i + 1], base) + ar[i - 1] + 997;
            if (suff[i] >= mod) suff[i] -= mod;
        }
    }

    PolyHash(const char* str)
        : PolyHash(vector<char> (str, str + strlen(str))) {}

    uint64_t get_hash(int l, int r){
        int64_t h = pref[r + 1] - modmul(base_pow[r - l + 1], pref[l]);
        return h < 0 ? h + mod : h;
    }

    uint64_t rev_hash(int l, int r){
        int64_t h = suff[l + 1] - modmul(base_pow[r - l + 1], suff[r + 2]);
        return h < 0 ? h + mod : h;
    }
};

string FileS="";
bool tstc=0;
void dothethingthatfindsthesolutiontotheproblem(){
    string s;
    cin>>s;
    vector<char>c;
    for(auto &i:s)c.push_back(i);
    PolyHash h=PolyHash(c);
    map<ll,ll>mp;
    ll ans=0;
    for(int i=0;i<sz(s);i++){
        int l=i,r=i;
        while(l>=0&&r<sz(s)&&s[l]==s[r]){
            ans=max(ans,++mp[h.get_hash(l,r)]*(r-l+1));
            r++;
            l--;
        }
    }
    for(int i=1;i<sz(s);i++){
        int l=i-1,r=i;
        while(l>=0&&r<sz(s)&&s[l]==s[r]){
            ans=max(ans,++mp[h.get_hash(l,r)]*(r-l+1));
            r++;
            l--;
        }
    }
    cout<<ans;
}


void File(){
    ifstream cin(FileS + ".in");
    ofstream cout(FileS + ".out");
}

int main(){

    send help

    if(FileS.size())File();

    int tc=1;
    if(tstc)cin>>tc;

    while(tc--){
        dothethingthatfindsthesolutiontotheproblem();
    }
}

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

palindrome.cpp: In instantiation of 'PolyHash::PolyHash(const std::vector<_Tp>&) [with T = char]':
palindrome.cpp:105:57:   required from here
palindrome.cpp:95:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
   95 |             if (pref[i] >= mod) pref[i] -= mod;
palindrome.cpp:100:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
  100 |             if (suff[i] >= mod) suff[i] -= mod;

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27