結果

問題 No.515 典型LCP
コンテスト
ユーザー btk
提出日時 2017-05-07 16:29:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 530 ms / 1,000 ms
コード長 1,533 bytes
コンパイル時間 1,623 ms
コンパイル使用メモリ 172,968 KB
実行使用メモリ 16,512 KB
最終ジャッジ日時 2024-09-14 14:47:03
合計ジャッジ時間 7,918 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}

typedef unsigned long long ULL;
typedef long long LL;
const ULL h=937919;

char str[912345];
int main(){
    int N;    scanf("%d",&N);
    vector<string> s(N);
    vector<vector<ULL>> hh(N);

    REP(i,N){
        scanf("%s",str);
        s[i]=str;
        hh[i].resize(s[i].size()+1);
        hh[i][0]=0;
        REP(j,s[i].size()){
            hh[i][j+1]=hh[i][j]*h+s[i][j];
        }
        
    }
    // return 0;
    LL x,d,M;
    scanf("%lld %lld %lld",&M,&x,&d);
    LL res=0;
    REP(q,M){
        LL i = x/(N-1)+1;
        LL j = x%(N-1)+1;
        if(i>j)swap(i,j);
        else j++;
        i--,j--;        
 
        int lb=0;
        int ub=min(s[i].size(),s[j].size())+1;
        while(ub-lb>1){
            const int mid=(ub+lb)/2;
            if(hh[i][mid]==hh[j][mid])lb=mid;
            else ub=mid;
        }
        res+=lb;
        

        x=(x+d)%(N*(N-1ll));
    }
    cout<<res<<endl;
    return 0;
}
0