結果
問題 | No.515 典型LCP |
ユーザー |
![]() |
提出日時 | 2017-05-06 00:17:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,532 bytes |
コンパイル時間 | 1,765 ms |
コンパイル使用メモリ | 174,396 KB |
実行使用メモリ | 16,768 KB |
最終ジャッジ日時 | 2024-09-14 10:06:39 |
合計ジャッジ時間 | 8,263 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 WA * 2 |
ソースコード
#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;}