結果

問題 No.515 典型LCP
ユーザー imulanimulan
提出日時 2017-05-06 03:26:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,146 bytes
コンパイル時間 1,886 ms
コンパイル使用メモリ 173,452 KB
実行使用メモリ 75,904 KB
最終ジャッジ日時 2024-09-14 12:15:30
合計ジャッジ時間 6,393 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

struct RollingHash{
    static const int MD = 3;
    static const vector<ll> hash_base, hash_mod;

    int n;
    vector<ll> hs[MD], pw[MD];

    RollingHash(){}
    RollingHash(const string &s){
        n = s.size();
        rep(i,MD){
            hs[i].assign(n+1,0);
            pw[i].assign(n+1,0);
            hs[i][0] = 0;
            pw[i][0] = 1;
            rep(j,n){
                pw[i][j+1] = pw[i][j]*hash_base[i] % hash_mod[i];
                hs[i][j+1] = (hs[i][j]*hash_base[i]+s[j]) % hash_mod[i];
            }
        }
    }

    // 1-index
    ll hash_value(int l, int r, int i){
        return ((hs[i][r] - hs[i][l]*pw[i][r-l])%hash_mod[i]+hash_mod[i])%hash_mod[i];
    }

    bool match(int l1, int r1, int l2, int r2){
        bool ret = true;
        rep(i,MD) ret &= (hash_value(l1-1,r1,i) == hash_value(l2-1,r2,i));
        return ret;
    }

    vector<ll> calc(int l, int r){
        vector<ll> ret(MD);
        rep(i,MD) ret[i]=hash_value(l-1,r,i);
        return ret;
    }
};
const vector<ll> RollingHash::hash_base{1009,1021,1013};
const vector<ll> RollingHash::hash_mod{1000000009,1000000007,1000000021};

const int N=100000;
RollingHash rh[N];
int sz[N];

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

    int n;
    cin >>n;

    rep(i,n)
    {
        string s;
        cin >>s;
        rh[i] = RollingHash(s);
        sz[i] = s.size();
    }

    int m;
    ll x,d;
    cin >>m >>x >>d;

    ll ans=0;
    while(m--)
    {
        // make query
        ll u=x/(n-1), v=x%(n-1);
        if(u>v) swap(u,v);
        else ++v;
        x = (x+d)%((ll)n*(n-1));

        // printf("u,v %lld, %lld\n", u,v);

        // solve
        int l=0, r=min(sz[u],sz[v])+1;
        while(r-l>1)
        {
            int mid=(l+r)/2;

            if(rh[u].calc(1,mid) == rh[v].calc(1,mid)) l=mid;
            else r=mid;
        }

        ans += l;
    }

    cout << ans << endl;
    return 0;
}
0