結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー chaemon
提出日時 2016-12-16 23:57:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,758 bytes
コンパイル時間 1,771 ms
コンパイル使用メモリ 172,876 KB
実行使用メモリ 32,644 KB
最終ジャッジ日時 2024-11-30 21:54:10
合計ジャッジ時間 3,133 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #includes {{{
#include<bits/stdc++.h>
using namespace std;
// }}}
// pre-written code {{{
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair
#define PB push_back
#define CLEAR(c,d) memset((c),(d),sizeof(c))
#define TO_STRING(VariableName) # VariableName
#define DB(c) cout<<TO_STRING(c)<<"="<<(c)<<endl
typedef long long Int;
typedef unsigned long long uInt;
typedef long double rn;
typedef pair<int,int> pii;
struct IO{ }io;//dummy
#define endl "\n"
IO& operator>>(IO &io,int &n){scanf("%d",&n);return io;}
IO& operator>>(IO &io,unsigned int &n){scanf("%u",&n);return io;}
IO& operator>>(IO &io,long long &n){scanf("%lld",&n);return io;}
IO& operator>>(IO &io,unsigned long long &n){scanf("%llu",&n);return io;}
IO& operator>>(IO &io,double &n){scanf("%lf",&n);return io;}
IO& operator>>(IO &io,long double &n){scanf("%Lf",&n);return io;}
IO& operator>>(IO &io,char *c){scanf("%s",c);return io;}
 
IO& operator<<(IO &io,const int &n){printf("%d",n);return io;}
IO& operator<<(IO &io,const unsigned int &n){printf("%u",n);return io;}
IO& operator<<(IO &io,const long long &n){printf("%lld",n);return io;}
IO& operator<<(IO &io,const unsigned long long &n){printf("%llu",n);return io;}
IO& operator<<(IO &io,const double &n){printf("%lf",n);return io;}
IO& operator<<(IO &io,const long double &n){printf("%Lf",n);return io;}
IO& operator<<(IO &io,const char c[]){printf("%s",c);return io;}
// }}}
const int P = 137;
const int D = 500010;
uInt p[D];
uInt pp[D],tail_p_ct[D];
string S;
pair<uInt,uInt> get2(int ii,int ij){
    uInt h = 0ull,rev_h = 0ull;
    for(int i=ii;i<ij;i++){
        h+=p[i]*(uInt)S[i];
        rev_h*=P;rev_h+=(uInt)S[i];
    }
    return make_pair(h,rev_h);
}
uInt get(int ii,int ij){
    uInt h = 0ull;
    for(int i=ii;i<ij;i++){
        h+=p[i]*(uInt)S[i];
    }
    return h;
}
struct Palin{
    int r,s;
    uInt hr,hs;
    int n;//n r-s, n-1 s-s
    int tail;
    Palin(int r,uInt hr,int s,uInt hs,int n,int tail):r(r),hr(hr),hs(hs),s(s),n(n),tail(tail){}
};
vector<Palin> vp;
//{{{ main function
int main() {
    memset(pp,0,sizeof(pp));
    cin>>S;
    uInt h = 0ull, rev_h = 0ull, t = 1ull;
    for(int i=0;i<S.size();i++){
        p[i] = t;
        t*=P;
    }
    uInt ct = 0;
    for(int i=S.size()-1;i>=0;i--){
        h+=p[S.size()-1-i]*(uInt)S[i];
        rev_h*=P;rev_h+=(uInt)S[i];
        if(h==rev_h){
            ct++;
        }
        tail_p_ct[i] = ct;
    }
    h = 0ull, rev_h = 0ull;
    for(int i=0;i<S.size();){
        h+=p[i]*(uInt)S[i];
        rev_h*=P;rev_h+=(uInt)S[i];
        i++;
        if(h==rev_h){
//          cerr<<"palindrome: "<<i<<endl;
            if(i>=2){
                int d;
                d = i - vp.back().tail;
//              cerr<<"palindrome: "<<i<<" "<<d<<endl;
                int r = i%d, s = d-r;
                if(vp.size()>0){
//                  cerr<<"count previous pp"<<endl;
//                  cerr<<r<<" "<<s<<endl;
                    uInt h = 0, rev_h = 0;
                    for(int i=r;i<r+s;){
                        h+=p[i-r]*(uInt)S[i];
                        rev_h*=P;rev_h+=(uInt)S[i];
                        i++;
                        if(h==rev_h){
//                          cerr<<"found: "<<r<<" "<<i<<endl;
                            //find rsrsrsrs or ssssss
                            int ct = 0;
                            if(ct<vp.back().n)pp[i]++;
                            while(1){
                                if(vp.back().r!=0){
                                    pair<uInt,uInt> u = get2(i,i+vp.back().r);
                                    if(u.first!=vp.back().hr)break;
                                    i+=vp.back().r;
                                    h+=p[vp.back().r]*u.first;
                                    rev_h*=p[vp.back().r];
                                    rev_h+=u.second;
                                }
                                pair<uInt,uInt> u = get2(i,i+vp.back().s);
                                if(u.first!=vp.back().hs)break;
                                i+=vp.back().s;
                                h+=p[vp.back().s]*u.first;
                                rev_h*=p[vp.back().s];
                                rev_h+=u.second;
                                ct++;
                                if(ct<vp.back().n)pp[i]++;
                            }
                        }
                    }
                }
                uInt hr = get(0,r), hs = get(r,r+s);
                int section_ct = 0;
                //r=0: ssssssss
                //r!=0: rsrsrsrs
                int i2 = i;
                uInt h2 = h, rev_h2 = rev_h;
                while(1){
                    section_ct++;
                    if(r!=0){
                        if(i2+r>S.size())break;
                        pair<uInt,uInt> u = get2(i2,i2+r);
                        if(u.first!=hr){
                            break;
                        }
                        i2+=r;
                        h2+=p[r]*u.first;
                        rev_h2*=p[r];
                        rev_h2+=u.second;
                    }
                    if(i2+s>S.size())break;
                    pair<uInt,uInt> u = get2(i2,i2+s);
                    if(u.first!=hs){
                        break;
                    }
                    i2+=s;
                    h2+=p[s]*u.first;
                    rev_h2*=p[s];
                    rev_h2+=u.second;
                }
//              cerr<<"insert: "<<i<<endl;
                vp.push_back(Palin(r,hr,s,hs,section_ct,i2));
                h = h2;
                rev_h2 = rev_h;
                i = i2;
            }else{
                vp.push_back(Palin(0,0,1,h,1,1));
            }
        }
    }
    /*
    REP(i,S.size())cout<<pp[i]<<" ";
    cout<<endl;
    REP(i,S.size())cout<<tail_p_ct[i]<<" ";
    cout<<endl;
    */
    uInt ans = 0;
    REP(i,S.size()){
        ans+=pp[i]*tail_p_ct[i+1];
    }
    cout<<ans<<endl;
    return 0;
}
//}}}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0