結果

問題 No.464 PPAP
ユーザー maimai
提出日時 2016-12-17 01:53:40
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 3,701 bytes
コンパイル時間 1,659 ms
コンパイル使用メモリ 168,180 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-20 18:38:13
合計ジャッジ時間 2,866 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,384 KB
testcase_10 AC 31 ms
4,380 KB
testcase_11 AC 7 ms
4,380 KB
testcase_12 AC 11 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,384 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 1 ms
4,384 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;

#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;
#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;
#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}
#define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}
#define ALL(v) (v).begin(),(v).end()
#define BIGINT 0x7FFFFFFF
#define E107 1000000007ll
void printbit(int u){if(u==0)cout<<0;else{int s=0,k=0;for(;0<u;u>>=1,k++)s=(s<<1)|(u&1);for(;0<k--;s>>=1)cout<<(s&1);}}

#define TIME chrono::system_clock::now()
#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())

template<typename T1,typename T2>
ostream& operator <<(ostream &o,const pair<T1,T2> p){o<<"("<<p.first<<":"<<p.second<<")";return o;}

class manacher{
public:
    vector<int> radius;
    
    manacher(){}
    manacher(const string& str){make(str);}
    
    void make(const string& str){
        // TODO:ざっくりとしか理解してないのでほぼコピペ
        // http://snuke.hatenablog.com/entry/2014/12/02/235837
        // abaaaa
        int length = str.size()*2-1;
        radius.resize(length);
        
        int c = 0;
        for (int i = 0; i < length; i++) {
            int l = c - (i-c);
            if (i+radius[l] < c+radius[c]) {
                radius[i] = radius[l];
            } else {
                int j = c+radius[c] - i;
                for (;i-j >= 0 && i+j < length ; j++){
                    if (((i^j)&1)==1) continue;
                    if (str[(i-j)/2] != str[(i+j)/2]) break;
                }
                radius[i] = j;
                c = i;
            }
        }
    }
    
    int operator[](int idx) const{
        return radius[idx];
    }
    size_t size() const{
        return radius.size();
    }
    
    void print(const string& str){
        for (int i=0;i<str.size();i++){
            cout << str[i] << " ";
        }
        cout << endl;
        for (int i=0;i<radius.size();i++){
            cout << radius[i];
        }
        cout << endl;
    }
    
};

int width,height;
int m,n;

string str;
manacher manatee;
ll back_imos[101010];

// 4th P
ll calc3(int index){
    if (manatee.size()-2<=index) return 0;
    //cout << "!" << index << endl;
    return back_imos[index+2];
}
// 2nd P
ll calc2(int index){
    int i;
    //cout << index << endl;
    if (manatee.size()-4<=index) return 0;
    //cout << index << endl;
    ll result = 0;
    for (i=index;i<manatee.size();i++){
        if (manatee[i] >= i-index+1){
            result += calc3(i-index+i+2);
        }
    }
    return result;
}
// 1st P
ll calc1(){
    int i;
    ll result = 0;
    for (i=0;i<manatee.size();i++){
        if (manatee[i] == i+1){
            result += calc2(i+i+2);
        }
    }
    return result;
}

void gen_back_imos(){
    int i,j,n;
    n = manatee.size();
    for (i=n-1;0<=i;i--){
        j = n-i-1;
        if (manatee[i] == j+1){
            back_imos[i-j]++;
        }
    }
    for (i=n-1;0<=i;i--){
        back_imos[i]+=back_imos[i+1];
    }
}

int main(){
    int i,j,k;
    int x,y,a,b;
    
    cin >> str;
    
    manatee.make(str);
    //manatee.print(str);
    
    gen_back_imos();
    //debuga(back_imos,29);
    
    cout << calc1() << endl;

    return 0;
}
0