結果

問題 No.515 典型LCP
ユーザー btkbtk
提出日時 2017-05-07 16:29:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 439 ms / 1,000 ms
コード長 1,533 bytes
コンパイル時間 1,486 ms
コンパイル使用メモリ 171,680 KB
実行使用メモリ 16,560 KB
最終ジャッジ日時 2023-10-12 16:08:17
合計ジャッジ時間 7,681 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 439 ms
16,560 KB
testcase_01 AC 425 ms
16,560 KB
testcase_02 AC 362 ms
10,600 KB
testcase_03 AC 2 ms
4,352 KB
testcase_04 AC 1 ms
4,352 KB
testcase_05 AC 367 ms
10,448 KB
testcase_06 AC 410 ms
10,480 KB
testcase_07 AC 350 ms
10,552 KB
testcase_08 AC 414 ms
10,656 KB
testcase_09 AC 340 ms
10,552 KB
testcase_10 AC 139 ms
10,612 KB
testcase_11 AC 135 ms
10,696 KB
testcase_12 AC 136 ms
10,564 KB
testcase_13 AC 408 ms
10,544 KB
testcase_14 AC 12 ms
10,656 KB
testcase_15 AC 348 ms
10,188 KB
testcase_16 AC 426 ms
10,196 KB
権限があれば一括ダウンロードができます

ソースコード

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