結果
問題 | No.515 典型LCP |
ユーザー | btk |
提出日時 | 2017-05-05 23:53:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 9,205 bytes |
コンパイル時間 | 2,130 ms |
コンパイル使用メモリ | 184,684 KB |
実行使用メモリ | 54,160 KB |
最終ジャッジ日時 | 2024-09-14 09:27:38 |
合計ジャッジ時間 | 13,648 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | AC | 3 ms
11,848 KB |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
ソースコード
#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; } /* sa[0]=n //空文字列 lcp[i]:=suffix[sa[i]]とsuffix[sa[i+1]]の共通高さ */ namespace sasa{ bool is_lms(int index, const std::vector<bool> &sl_seq){ if(index+1 == (int)sl_seq.size())return true; if(0 < index && index < (int)sl_seq.size()){ return sl_seq[index] && !sl_seq[index-1]; } return false; } std::vector<int> get_bucket(int* seq, const int n, const int alphabet_size){ std::vector<int> bucket(alphabet_size); for(int i=0 ; i<n ; i++)bucket[seq[i]]++; for(int i=0 ; i<alphabet_size-1 ; i++)bucket[i+1] += bucket[i]; return bucket; } void sort_type_l(int* seq, const int n, const std::vector<bool> &is_type_s, int* arr, const int alphabet_size){ std::vector<int> bucket = get_bucket(seq, n, alphabet_size); for(int i=0 ; i<n ; i++){ if(arr[i] != -1 && arr[i]>0 && !is_type_s[arr[i]-1]){ arr[bucket[seq[arr[i]-1]-1]++] = arr[i]-1; } } } void sort_type_s(int* seq, const int n, const std::vector<bool> &is_type_s, int* arr, const int alphabet_size){ std::vector<int> bucket = get_bucket(seq, n, alphabet_size); for(int i=n-1 ; i>=0 ; i--){ if(arr[i] != -1 && arr[i]>0 && is_type_s[arr[i]-1]){ arr[--bucket[seq[arr[i]-1]]] = arr[i]-1; } } } void create_suffix_array(int* arr, int* seq, const int n, const int alphabet_size){ for(int i=0 ; i<n ; i++)arr[i] = -1; std::vector<bool> is_type_s(n); is_type_s[n-1] = true; for(int i=n-2 ; i>=0 ; i--){ if(seq[i] == seq[i+1])is_type_s[i] = is_type_s[i+1]; else is_type_s[i] = seq[i] < seq[i+1]; } std::vector<int> bucket = get_bucket(seq, n, alphabet_size); for(int i=0 ; i < n ; i++){ if(is_lms(i, is_type_s))arr[--bucket[seq[i]]] = i; } sort_type_l(seq, n, is_type_s, arr, alphabet_size); sort_type_s(seq, n, is_type_s, arr, alphabet_size); // LMS-substringの元の数値列における位置を辞書順に左詰めで格納する int num_lms = 0; for(int i=0 ; i<n ; i++){ if(is_lms(arr[i], is_type_s))arr[num_lms++] = arr[i]; } // 辞書順以外を一旦クリア for(int i=num_lms ; i<n ; i++)arr[i] = -1; // LMS-substringのidを元の数値列における出現順で空いているところに格納する arr[num_lms + arr[0]/2] = 0; for(int i=1 ; i<num_lms ; i++){ int p = arr[i-1], q = arr[i]; bool same = i != 1; // 番兵回避 for(int w=1 ; same ; w++){ if(seq[p+w]!=seq[q+w])same = false; bool p_is_lms = is_lms(p+w, is_type_s); bool q_is_lms = is_lms(q+w, is_type_s); if(!p_is_lms && !q_is_lms)continue; if(!(p_is_lms && q_is_lms))same = false; break; } if(same){ arr[num_lms + q/2] = arr[num_lms + p/2]; }else{ arr[num_lms + q/2] = arr[num_lms + p/2] + 1; } } // LMS-substringのidを元の数値列における出現順で右詰で格納する int next_alphabet_size = arr[num_lms + arr[num_lms-1]/2] + 1; for(int i=n-1, p=n-1 ; i >= num_lms ; i--){ if(arr[i] != -1)arr[p--] = arr[i]; } // 同じLMS-substringがある場合は再帰的に順序を求めるa if(next_alphabet_size != num_lms){ create_suffix_array(arr, arr+n-num_lms, num_lms, next_alphabet_size); for(int i=0 ; i < num_lms ; i++)arr[n-num_lms+arr[i]] = i; for(int i=0, p=0 ; i < n ; i++){ if(is_lms(i, is_type_s)){ arr[arr[n-num_lms+p]] = i; p++; } } } // 辞書順以外を一旦クリア for(int i=num_lms ; i<n ; i++)arr[i] = -1; // 配列の末尾から正規の位置に詰めなおす bucket = get_bucket(seq, n, alphabet_size); for(int i=num_lms-1 ; i >= 0 ; i--){ bucket[seq[arr[i]]]--; std::swap(arr[bucket[seq[arr[i]]]], arr[i]); } sort_type_l(seq, n, is_type_s, arr, alphabet_size); sort_type_s(seq, n, is_type_s, arr, alphabet_size); } int latte[912345]; int malta[912345]; std::vector<int> create_suffix_array_from_string(const std::string &str){ std::set<char> _alphabet(str.begin(), str.end()); std::vector<char> alphabet(_alphabet.begin(), _alphabet.end()); int n = str.size()+1; int* seq = latte; int* arr = malta; for(int i=0 ; i < n-1 ; i++)seq[i] = lower_bound(alphabet.begin(), alphabet.end(), str[i]) - alphabet.begin() + 1; create_suffix_array(arr, seq, n, alphabet.size()); return std::vector<int>(arr, arr+n); } }; namespace SA { int n, k; int R[912345]; int T[912345]; bool compare_sa(int i, int j) { if (R[i] != R[j])return R[i] < R[j]; else { int ri = i + k <= n ? R[i + k] : -1; int rj = j + k <= n ? R[j + k] : -1; return ri < rj; } } vector<int> construct_sa(string& S) { return sasa::create_suffix_array_from_string(S); n = S.size(); vector<int> sa(n + 1); for (int i = 0; i <= n; i++) { sa[i] = i; R[i] = i < n ? S[i] : -1; } for (k = 1; k <= n; k *= 2) { sort(sa.begin(), sa.end(), compare_sa); T[sa[0]] = 0; for (int i = 1; i <= n; i++) T[sa[i]] = T[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0); for (int i = 0; i <= n; i++) R[i] = T[i]; } return sa; } vector<int> construct_lcp(string& S, vector<int> &sa) { n = S.size(); for (int i = 0; i <= n; i++)R[sa[i]] = i; int h = 0; vector<int> lcp(n + 1, 0); for (int i = 0; i < n; i++) { int j = sa[R[i] - 1]; if (h > 0)h--; for (; j + h < n&&i + h < n; h++) { if (S[j + h] != S[i + h])break; } lcp[R[i] - 1] = h; } return lcp; } } namespace TABLE{ #define SIZE 3000000 int mem[2][SIZE]; //#defube CNT 100 //int cnt=0; //int mems[CNT][SIZE]; }; template <typename T> class min_sparse_table{ private: T *L,*R;int _size; void build(){ for(int k = _size,b=1 ;b*2<=_size; k+=_size,b<<=1) for(int i = 0; i < _size; i++){ if(i+b*2<=_size) L[k+i]=min(L[k-_size+i],L[k-_size+i+b]); if(i-b*2>=-1) R[k+i]=min(R[k-_size+i],R[k-_size+i-b]); } } public:/*methods*/ int size(){return _size;} T get(int l,int r){ int k=(31-__builtin_clz(r-l+1))*_size; return min(L[k+l],R[k+r]); } min_sparse_table(std::vector<T> &v) :L(TABLE::mem[0]),R(TABLE::mem[1]){ _size=v.size(); for(int i = 0; i < _size; i++)L[i]=R[i]=v[i]; build(); } min_sparse_table(T* v,int n) :L(TABLE::mem[0]),R(TABLE::mem[1]){ _size=n; for(int i = 0; i < _size; i++)L[i]=R[i]=v[i]; build(); } }; char s[912345]; int main(){ int N; scanf("%d",&N); char *ss=s; vector<int> id(N+1); int len=0; REP(i,N){ scanf("%s",ss); id[i]=len; while(*ss !='\0'){ ss++;len++; } *(ss++)='$';len++; } id.back()=len; *(ss++)='\0'; string str=s; LL x,d,M; scanf("%lld %lld %lld",&M,&x,&d); auto sa = SA::construct_sa(str); auto cww=sa; REP(i,sa.size()){ //cout<<sa[i]<<endl; cww[sa[i]]=i; } auto lcp = SA::construct_lcp(str,sa); min_sparse_table<int> rmq(lcp); 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 ij=min(id[i+1]-id[i],id[j+1]-id[j])-1; i=cww[id[i]]; j=cww[id[j]]; if(i>j)swap(i,j); if(i==j){ res+=id[i+1]-id[i]-1; //cout<<"a"<<endl; } else { int k=rmq.get(i,j-1); res+=min(k,ij); //cout<<k<<endl; } x=(x+d)%(N*(N-1)); } printf("%lld\n",res); return 0; }