結果

問題 No.765 ukuku 2
ユーザー rickythetarickytheta
提出日時 2018-12-13 00:56:34
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 134 ms / 3,000 ms
コード長 3,653 bytes
コンパイル時間 1,624 ms
コンパイル使用メモリ 163,104 KB
実行使用メモリ 7,112 KB
最終ジャッジ日時 2024-09-25 03:54:13
合計ジャッジ時間 5,168 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,816 KB
testcase_01 AC 4 ms
6,816 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 4 ms
6,940 KB
testcase_04 AC 4 ms
6,940 KB
testcase_05 AC 4 ms
6,940 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 4 ms
6,944 KB
testcase_09 AC 4 ms
6,940 KB
testcase_10 AC 4 ms
6,944 KB
testcase_11 AC 4 ms
6,944 KB
testcase_12 AC 4 ms
6,944 KB
testcase_13 AC 4 ms
6,940 KB
testcase_14 AC 4 ms
6,944 KB
testcase_15 AC 4 ms
6,940 KB
testcase_16 AC 3 ms
6,944 KB
testcase_17 AC 4 ms
6,944 KB
testcase_18 AC 4 ms
6,940 KB
testcase_19 AC 4 ms
6,944 KB
testcase_20 AC 4 ms
6,940 KB
testcase_21 AC 4 ms
6,940 KB
testcase_22 AC 4 ms
6,944 KB
testcase_23 AC 4 ms
6,944 KB
testcase_24 AC 3 ms
6,944 KB
testcase_25 AC 4 ms
6,940 KB
testcase_26 AC 4 ms
6,940 KB
testcase_27 AC 4 ms
6,944 KB
testcase_28 AC 4 ms
6,944 KB
testcase_29 AC 3 ms
6,940 KB
testcase_30 AC 79 ms
6,940 KB
testcase_31 AC 84 ms
6,944 KB
testcase_32 AC 80 ms
6,940 KB
testcase_33 AC 62 ms
6,940 KB
testcase_34 AC 62 ms
6,948 KB
testcase_35 AC 123 ms
6,940 KB
testcase_36 AC 123 ms
6,944 KB
testcase_37 AC 134 ms
6,940 KB
testcase_38 AC 122 ms
6,940 KB
testcase_39 AC 113 ms
6,940 KB
testcase_40 AC 65 ms
6,940 KB
testcase_41 AC 86 ms
6,940 KB
testcase_42 AC 83 ms
6,940 KB
testcase_43 AC 85 ms
6,944 KB
testcase_44 AC 75 ms
7,112 KB
testcase_45 AC 129 ms
6,944 KB
testcase_46 AC 97 ms
6,944 KB
testcase_47 AC 90 ms
6,984 KB
testcase_48 AC 87 ms
6,940 KB
testcase_49 AC 109 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:28:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |   scanf("%s",s);
      |   ~~~~~^~~~~~~~

ソースコード

diff # 

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

typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))

// const ll B = 10007;
const ll B = 10007;
const ll MOD = 1000000009;
int bpow[252521];

int n;
char s[252521];
char rs[252521];
int hsh[252521], rhsh[252521];

int rhash(int *h, int l, int r){
  // s[l,...,r-1]
  return (h[r] - (ll)h[l]*bpow[r-l]%MOD + MOD) % MOD;
}

int main(){
  scanf("%s",s);
  n = strlen(s);
  REP(i,n)rs[n-1-i] = s[i];
  REP(i,n)hsh[i+1] = ((ll)hsh[i]*B + s[i]) % MOD;
  REP(i,n)rhsh[i+1] = ((ll)rhsh[i]*B + rs[i]) % MOD;
  bpow[0] = 1;
  FOR(i,1,252521)bpow[i] = (ll)bpow[i-1]*B%MOD;

  int ans = 1;
  // center character is s[i]
  REP(i,n){
    // no remove
    int low = 0, high = min(i, n-1-i)+1;
    while(low+1<high){
      int len = (low+high)/2;
      int lefthash = rhash(hsh, i-len, i);
      int righthash = rhash(rhsh, n-1-len-i, n-i-1);
      if(lefthash == righthash){
        low = len;
      }else{
        high = len;
      }
    }
    int clen = low;
    CHMAX(ans, 2*clen);  // remove center character
    if(2*clen+1 < n)CHMAX(ans, 2*clen+1); // remove other character
    // remove left
    if(i-clen > 0){
      int l = i-clen-1;
      int r = i+clen;
      int low = 0, high = min(l, n-1-r)+1;
      while(low+1<high){
        int len = (low+high)/2;
        int lefthash = rhash(hsh, l-len, l);
        int righthash = rhash(rhsh, n-1-len-r, n-r-1);
        if(lefthash == righthash){
          low = len;
        }else{
          high = len;
        }
      }
      CHMAX(ans, 2*clen+2*low+1);
    }
    // remove right
    if(i+clen < n-1){
      int l = i-clen;
      int r = i+clen+1;
      int low = 0, high = min(l, n-1-r)+1;
      while(low+1<high){
        int len = (low+high)/2;
        int lefthash = rhash(hsh, l-len, l);
        int righthash = rhash(rhsh, n-1-len-r, n-r-1);
        if(lefthash == righthash){
          low = len;
        }else{
          high = len;
        }
      }
      CHMAX(ans, 2*clen+2*low+1);
    }
  }
  // center character is s[i], s[i+1]
  REP(i,n-1)if(s[i]==s[i+1]){
    // no remove
    int l = i, r = i+1;
    int low = 0, high = min(l, n-1-r)+1;
    while(low+1<high){
      int len = (low+high)/2;
      int lefthash = rhash(hsh, l-len, l);
      int righthash = rhash(rhsh, n-1-len-r, n-r-1);
      if(lefthash == righthash){
        low = len;
      }else{
        high = len;
      }
    }
    int clen = low;
    CHMAX(ans, 2*clen+1);  // remove center character
    if(2*clen+2 < n)CHMAX(ans, 2*clen+2); // remove other character
    // remove left
    if(i-clen > 0){
      int l = i-clen-1;
      int r = i+1+clen;
      int low = 0, high = min(l, n-1-r)+1;
      while(low+1<high){
        int len = (low+high)/2;
        int lefthash = rhash(hsh, l-len, l);
        int righthash = rhash(rhsh, n-1-len-r, n-r-1);
        if(lefthash == righthash){
          low = len;
        }else{
          high = len;
        }
      }
      CHMAX(ans, 2*clen+2+2*low);
    }
    // remove right
    if(i+1+clen < n-1){
      int l = i-clen;
      int r = i+1+clen+1;
      int low = 0, high = min(l, n-1-r)+1;
      while(low+1<high){
        int len = (low+high)/2;
        int lefthash = rhash(hsh, l-len, l);
        int righthash = rhash(rhsh, n-1-len-r, n-r-1);
        if(lefthash == righthash){
          low = len;
        }else{
          high = len;
        }
      }
      CHMAX(ans, 2*clen+2+2*low);
    }
  }
  printf("%d\n",ans);
  return 0;
}
0