結果

問題 No.765 ukuku 2
ユーザー rickythetarickytheta
提出日時 2018-12-13 00:56:34
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 135 ms / 3,000 ms
コード長 3,653 bytes
コンパイル時間 1,427 ms
コンパイル使用メモリ 163,612 KB
実行使用メモリ 7,072 KB
最終ジャッジ日時 2023-10-25 08:47:23
合計ジャッジ時間 4,759 ms
ジャッジサーバーID
(参考情報)
judge14 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,404 KB
testcase_01 AC 4 ms
6,404 KB
testcase_02 AC 4 ms
6,404 KB
testcase_03 AC 4 ms
6,404 KB
testcase_04 AC 4 ms
6,404 KB
testcase_05 AC 4 ms
6,404 KB
testcase_06 AC 4 ms
6,404 KB
testcase_07 AC 4 ms
6,404 KB
testcase_08 AC 4 ms
6,404 KB
testcase_09 AC 4 ms
6,404 KB
testcase_10 AC 4 ms
6,404 KB
testcase_11 AC 4 ms
6,404 KB
testcase_12 AC 4 ms
6,404 KB
testcase_13 AC 4 ms
6,404 KB
testcase_14 AC 4 ms
6,404 KB
testcase_15 AC 4 ms
6,404 KB
testcase_16 AC 4 ms
6,404 KB
testcase_17 AC 4 ms
6,404 KB
testcase_18 AC 4 ms
6,404 KB
testcase_19 AC 4 ms
6,404 KB
testcase_20 AC 5 ms
6,404 KB
testcase_21 AC 4 ms
6,404 KB
testcase_22 AC 4 ms
6,404 KB
testcase_23 AC 4 ms
6,404 KB
testcase_24 AC 4 ms
6,404 KB
testcase_25 AC 4 ms
6,404 KB
testcase_26 AC 4 ms
6,404 KB
testcase_27 AC 5 ms
6,404 KB
testcase_28 AC 4 ms
6,404 KB
testcase_29 AC 4 ms
6,404 KB
testcase_30 AC 80 ms
7,004 KB
testcase_31 AC 84 ms
6,988 KB
testcase_32 AC 80 ms
6,888 KB
testcase_33 AC 62 ms
7,072 KB
testcase_34 AC 63 ms
7,072 KB
testcase_35 AC 122 ms
7,072 KB
testcase_36 AC 122 ms
7,072 KB
testcase_37 AC 135 ms
7,072 KB
testcase_38 AC 122 ms
7,072 KB
testcase_39 AC 114 ms
7,072 KB
testcase_40 AC 66 ms
7,012 KB
testcase_41 AC 86 ms
7,060 KB
testcase_42 AC 84 ms
7,072 KB
testcase_43 AC 86 ms
7,032 KB
testcase_44 AC 75 ms
7,040 KB
testcase_45 AC 129 ms
7,072 KB
testcase_46 AC 97 ms
7,028 KB
testcase_47 AC 90 ms
7,072 KB
testcase_48 AC 88 ms
7,072 KB
testcase_49 AC 109 ms
7,072 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