Submission #7554966


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using VV = vector<VI>;
using VS = vector<string>;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")
#define pb(s) push_back(s)
#define SZ(x) ((int)(x).size())

void no(){p_no(); exit(0);}
void yes(){p_yes(); exit(0);}

const ll mod = 1e9 + 7;
const ll inf = 1e18;

template< unsigned mod >
struct RollingHash {
  vector< unsigned > hashed, power;

  inline unsigned mul(unsigned a, unsigned b) const {
    unsigned long long x = (unsigned long long) a * b;
    unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
    asm("divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod));
    return m;
  }

  RollingHash(const string &s, unsigned base = 10007) {
    int sz = (int) s.size();
    hashed.assign(sz + 1, 0);
    power.assign(sz + 1, 0);
    power[0] = 1;
    for(int i = 0; i < sz; i++) {
      power[i + 1] = mul(power[i], base);
      hashed[i + 1] = mul(hashed[i], base) + s[i];
      if(hashed[i + 1] >= mod) hashed[i + 1] -= mod;
    }
  }

  unsigned get(int l, int r) const {
    unsigned ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
    if(ret >= mod) ret -= mod;
    return ret;
  }

  unsigned connect(unsigned h1, int h2, int h2len) const {
    unsigned ret = mul(h1, power[h2len]) + h2;
    if(ret >= mod) ret -= mod;
    return ret;
  }

  int LCP(const RollingHash< mod > &b, int l1, int r1, int l2, int r2) {
    int len = min(r1 - l1, r2 - l2);
    int low = -1, high = len + 1;
    while(high - low > 1) {
      int mid = (low + high) / 2;
      if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
      else high = mid;
    }
    return (low);
  }
};

using RH = RollingHash< 1000000007 >;
using RH2 = RollingHash< 1000000009 >;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; cin >> N;
    string s; cin >> s;

    // 存在しない場合をチェック
    map<char, ll> mp;
    for(char c : s){
      mp[c]++;
    }
    if(mp.size()==N){
      p(0);
      return 0;
    }

    RH rh(s);
    RH rh2(s, 9973);

    ll left = 1; // can
    ll right = N/2+1; // can't

    ll ma = 0;
    while(left+1!=right){
      ll L = (left+right)/2; // この長さで見つけられるか
      bool found = false;
      
      map<pair<ll,ll>, ll> mp;
      for(int i=0; i<=N-L; i++){
        ll hash0 = rh.get(i, i+L);
        ll hash1 = rh2.get(i, i+L);
        auto pa = make_pair(hash0, hash1);
        if(mp.count(pa)>0){
          // hit?
          ll last_index = mp[pa];
          if(i-last_index>=L){
            found = true;
            chmax(ma, L);
            break;
          }
        }else{
          mp[pa] = i;
        }
      }
      if(found){
        left = L;
      }else{
        right = L;
      }
    }

    p(ma);
    return 0;
}

Submission Info

Submission Time
Task E - Who Says a Pun?
User peroon
Language C++14 (GCC 5.4.1)
Score 500
Code Size 3405 Byte
Status
Exec Time 14 ms
Memory 640 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
× 3
× 70
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 01-handmade-11, 01-handmade-12, 02-binary-13, 02-binary-14, 02-binary-15, 02-binary-16, 02-binary-17, 02-binary-18, 02-binary-19, 02-binary-20, 02-binary-21, 02-binary-22, 02-binary-23, 03-BigRandom-24, 03-BigRandom-25, 03-BigRandom-26, 03-BigRandom-27, 03-BigRandom-28, 03-BigRandom-29, 03-BigRandom-30, 03-BigRandom-31, 03-BigRandom-32, 03-BigRandom-33, 03-BigRandom-34, 03-BigRandom-35, 03-BigRandom-36, 03-BigRandom-37, 03-BigRandom-38, 03-BigRandom-39, 03-BigRandom-40, 03-BigRandom-41, 03-BigRandom-42, 03-BigRandom-43, 03-BigRandom-44, 03-BigRandom-45, 03-BigRandom-46, 03-BigRandom-47, 03-BigRandom-48, 03-BigRandom-49, 03-BigRandom-50, 03-BigRandom-51, 03-BigRandom-52, 03-BigRandom-53, 03-BigRandom-54, 04-zero-55, 04-zero-56, 05-AllRandom-57, 05-AllRandom-58, 05-AllRandom-59, 05-AllRandom-60, 05-AllRandom-61, 05-AllRandom-62, 05-AllRandom-63, 05-AllRandom-64, 05-AllRandom-65, 05-AllRandom-66, 05-AllRandom-67, 05-AllRandom-68, 05-AllRandom-69
Case Name Status Exec Time Memory
00-sample-00 1 ms 256 KB
00-sample-01 1 ms 256 KB
00-sample-02 1 ms 256 KB
01-handmade-03 2 ms 384 KB
01-handmade-04 8 ms 512 KB
01-handmade-05 8 ms 512 KB
01-handmade-06 8 ms 512 KB
01-handmade-07 8 ms 512 KB
01-handmade-08 2 ms 384 KB
01-handmade-09 12 ms 640 KB
01-handmade-10 11 ms 640 KB
01-handmade-11 3 ms 512 KB
01-handmade-12 5 ms 512 KB
02-binary-13 9 ms 640 KB
02-binary-14 11 ms 640 KB
02-binary-15 9 ms 512 KB
02-binary-16 11 ms 640 KB
02-binary-17 12 ms 640 KB
02-binary-18 10 ms 640 KB
02-binary-19 7 ms 512 KB
02-binary-20 8 ms 512 KB
02-binary-21 7 ms 512 KB
02-binary-22 7 ms 512 KB
02-binary-23 6 ms 512 KB
03-BigRandom-24 7 ms 512 KB
03-BigRandom-25 8 ms 512 KB
03-BigRandom-26 7 ms 512 KB
03-BigRandom-27 9 ms 512 KB
03-BigRandom-28 10 ms 512 KB
03-BigRandom-29 9 ms 512 KB
03-BigRandom-30 10 ms 512 KB
03-BigRandom-31 8 ms 512 KB
03-BigRandom-32 10 ms 512 KB
03-BigRandom-33 9 ms 512 KB
03-BigRandom-34 7 ms 512 KB
03-BigRandom-35 8 ms 512 KB
03-BigRandom-36 8 ms 512 KB
03-BigRandom-37 7 ms 512 KB
03-BigRandom-38 8 ms 512 KB
03-BigRandom-39 8 ms 512 KB
03-BigRandom-40 8 ms 512 KB
03-BigRandom-41 8 ms 512 KB
03-BigRandom-42 8 ms 512 KB
03-BigRandom-43 8 ms 512 KB
03-BigRandom-44 8 ms 512 KB
03-BigRandom-45 9 ms 512 KB
03-BigRandom-46 8 ms 512 KB
03-BigRandom-47 9 ms 512 KB
03-BigRandom-48 7 ms 512 KB
03-BigRandom-49 7 ms 512 KB
03-BigRandom-50 8 ms 512 KB
03-BigRandom-51 8 ms 512 KB
03-BigRandom-52 8 ms 512 KB
03-BigRandom-53 8 ms 512 KB
03-BigRandom-54 8 ms 512 KB
04-zero-55 1 ms 256 KB
04-zero-56 1 ms 256 KB
05-AllRandom-57 12 ms 640 KB
05-AllRandom-58 11 ms 640 KB
05-AllRandom-59 13 ms 640 KB
05-AllRandom-60 13 ms 640 KB
05-AllRandom-61 13 ms 640 KB
05-AllRandom-62 11 ms 640 KB
05-AllRandom-63 11 ms 640 KB
05-AllRandom-64 13 ms 640 KB
05-AllRandom-65 11 ms 640 KB
05-AllRandom-66 13 ms 640 KB
05-AllRandom-67 13 ms 640 KB
05-AllRandom-68 12 ms 640 KB
05-AllRandom-69 14 ms 640 KB