結果

問題 No.464 PPAP
コンテスト
ユーザー walkre
提出日時 2017-05-23 10:22:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 1,737 bytes
コンパイル時間 1,564 ms
コンパイル使用メモリ 172,936 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-19 11:37:26
合計ジャッジ時間 2,475 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

vector<int> manacher(const string& s){
    vector<int> rad(s.size());
    int i=0,j=0;
    while(i<s.size()){
        while(i-j>=0 and i+j<s.size() and s[i-j]==s[i+j]) ++j;
        rad[i]=j;
        int k=1;
        while(i-k>=0 and i+k<s.size() and k+rad[i-k]<j){
            rad[i+k]=rad[i-k];
            ++k;
        }
        i+=k;
        j-=k;
    }
    return rad;
}

//[l,r]
bool is_palindrome(const vector<int> &rad,int l,int r){
    l=l*2+1;
    r=r*2+1;
    int c=(l+r)/2;
    return r<c+rad[c];
}
string insert_dollar(const string& s){
    string t("$");
    for(int i=0; i<s.size(); ++i) t+=s[i]+string("$");
    return t;
}

void solve(){
    string s;
    cin >> s;
    vector<i64> pp(s.size());
    vector<int> rad=manacher(insert_dollar(s));
    rep(i,0,s.size()){
        rep(j,i+1,s.size()){
            if(is_palindrome(rad,0,i) and is_palindrome(rad,i+1,j)) ++pp[j];
        }
    }
    i64 ans=0;
    rep(i,0,s.size()) rep(j,i+2,s.size()) if(is_palindrome(rad,j,s.size()-1)) ans+=pp[i];
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}
0