結果

問題 No.515 典型LCP
ユーザー btkbtk
提出日時 2017-05-06 00:17:57
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,532 bytes
コンパイル時間 1,872 ms
コンパイル使用メモリ 171,796 KB
実行使用メモリ 16,708 KB
最終ジャッジ日時 2023-10-12 11:13:58
合計ジャッジ時間 8,327 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 377 ms
10,620 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 368 ms
10,416 KB
testcase_06 AC 412 ms
10,448 KB
testcase_07 AC 352 ms
10,420 KB
testcase_08 AC 417 ms
10,648 KB
testcase_09 AC 346 ms
10,664 KB
testcase_10 AC 142 ms
10,640 KB
testcase_11 AC 136 ms
10,512 KB
testcase_12 AC 140 ms
10,672 KB
testcase_13 AC 411 ms
10,484 KB
testcase_14 AC 13 ms
10,356 KB
testcase_15 AC 347 ms
10,176 KB
testcase_16 AC 427 ms
10,176 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-1));
    }
    cout<<res<<endl;
    return 0;
}
0