結果

問題 No.515 典型LCP
ユーザー kotatsugamekotatsugame
提出日時 2020-02-07 07:23:19
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 685 ms / 1,000 ms
コード長 4,519 bytes
コンパイル時間 1,159 ms
コンパイル使用メモリ 90,996 KB
実行使用メモリ 98,180 KB
最終ジャッジ日時 2024-09-25 07:11:55
合計ジャッジ時間 8,017 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 685 ms
98,180 KB
testcase_01 AC 534 ms
91,420 KB
testcase_02 AC 320 ms
80,248 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 333 ms
85,140 KB
testcase_06 AC 339 ms
84,432 KB
testcase_07 AC 330 ms
85,080 KB
testcase_08 AC 357 ms
81,704 KB
testcase_09 AC 267 ms
80,000 KB
testcase_10 AC 261 ms
80,216 KB
testcase_11 AC 263 ms
80,988 KB
testcase_12 AC 259 ms
80,296 KB
testcase_13 AC 260 ms
80,244 KB
testcase_14 AC 154 ms
81,096 KB
testcase_15 AC 330 ms
84,588 KB
testcase_16 AC 327 ms
85,604 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:202:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  202 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
using namespace std;
//construct SA by SA-IS O(N)
#include<string>
#include<vector>
struct SA{
	string s;
	vector<int>sa;
	SA(const string&s_):s(s_)
	{
		sa=build(vector<int>(s.begin(),s.end()),123);
	}
	vector<int>induced_sort(const vector<int>&S,const vector<int>&id,const vector<bool>&SL,vector<int>last)
	{
		vector<int>first(last);
		vector<int>ret(id.size());
		ret[0]=id[0];
		for(int i=0;i<id.size();i++)
		{
			if(id[i]>=1&&!SL[id[i]-1])
			{
				ret[first[S[id[i]-1]-1]++]=id[i]-1;
			}
			else if(ret[i]>=1&&!SL[ret[i]-1])
			{
				ret[first[S[ret[i]-1]-1]++]=ret[i]-1;
			}
		}
		for(int i=id.size();i--;)
		{
			if(ret[i]>=1&&SL[ret[i]-1])
			{
				ret[--last[S[ret[i]-1]]]=ret[i]-1;
			}
		}
		return ret;
	}
	vector<int>build(vector<int>S,int maxval)
	{
		if(S.size()<=1)
		{
			return S.empty()?(vector<int>){0}:(vector<int>){1,0};
		}
		S.push_back(0);
		vector<int>cnt(maxval,0);
		vector<bool>SL(S.size());//S=>true,L=>false
		for(int i=S.size();i--;)
		{
			cnt[S[i]]+=1;
			SL[i]=i+1==S.size()||S[i]<S[i+1]||S[i]==S[i+1]&&SL[i+1];
		}
		for(int i=1;i<maxval;i++)cnt[i]+=cnt[i-1];
		vector<int>last(cnt);
		vector<int>id(S.size());
		vector<int>is_LMS(S.size());
		int LMScnt=0;
		for(int i=1;i<S.size();i++)
		{
			if(!SL[i-1]&&SL[i])
			{
				is_LMS[i]=1;
				id[--cnt[S[i]]]=i;
				LMScnt+=1;
			}
		}
		id=induced_sort(S,id,SL,last);
		int LMSsub=1;
		int pre=-1;
		is_LMS[id[0]]=LMSsub++;
		for(int i=1;i<id.size();i++)
		{
			if(is_LMS[id[i]])
			{
				if(pre>=0&&S[pre]==S[id[i]])
				{
					int k;
					for(k=1;S[pre+k]==S[id[i]+k]&&!is_LMS[pre+k]&&!is_LMS[id[i]+k];k++);
					LMSsub-=S[pre+k]==S[id[i]+k]&&is_LMS[pre+k]&&is_LMS[id[i]+k];
				}
				pre=id[i];
				is_LMS[id[i]]=LMSsub++;
			}
		}
		vector<int>newstr(LMScnt);
		vector<int>rev(LMScnt);
		int counter=0;
		for(int i=0;i<S.size();i++)
		{
			if(is_LMS[i])
			{
				newstr[counter]=is_LMS[i];
				rev[counter]=i;
				counter+=1;
			}
		}
		vector<int>sortedLMS=build(newstr,LMSsub);
		id.assign(S.size(),0);
		for(int i=1;i<sortedLMS.size();i++)
		{
			int I=rev[sortedLMS[i]];
			id[cnt[S[I]]++]=I;
		}
		return induced_sort(S,id,SL,last);
	}
	int operator[](int i)const{return sa[i];}
	int lower_bound(const string&t)const
	{
		int L=-1,R=sa.size();
		while(R-L>1)
		{
			int M=L+R>>1;
			if(s.compare(sa[M],t.size(),t)>=0)R=M;
			else L=M;
		}
		return R;
	}
	int upper_bound(const string&t)const
	{
		int L=-1,R=sa.size();
		while(R-L>1)
		{
			int M=L+R>>1;
			if(s.compare(sa[M],t.size(),t)<=0)L=M;
			else R=M;
		}
		return R;
	}
	bool contain(const string&t)const
	{
		int id=lower_bound(t);
		return id<sa.size()&&s.compare(sa[id],t.size(),t)==0;
	}
	int size()const{return sa.size();}
};
//construct LCP O(N) require SA
struct LCP{
	vector<int>lcp;
	LCP(const SA&sa)
	{
		int n=sa.size()-1;
		lcp.assign(n,0);
		vector<int>rank(n+1);
		for(int i=0;i<=n;i++)rank[sa[i]]=i;
		int h=0;
		lcp[0]=0;
		for(int i=0;i<n;i++)
		{
			int j=sa[rank[i]-1];
			h-=h>0;
			for(;i+h<n&&j+h<n&&sa.s[i+h]==sa.s[j+h];h++);
			lcp[rank[i]-1]=h;
		}
	}
	int operator[](int i)const{return lcp[i];}
	int size()const{return lcp.size();}
};
//Disjoint Sparse Table
#include<vector>
#include<functional>
template<typename T>
struct DST{
	function<T(T,T)>calcfn;
	int n;
	vector<vector<T> >dat;
	DST(const vector<T>&v={},
		function<T(T,T)>calcfn_=[](T a,T b){return a<b?a:b;}
	):calcfn(calcfn_)
	{
		n=v.size();
		dat.push_back(v);
		for(int i=2;i<n;i<<=1)
		{
			dat.push_back(vector<T>(n));
			for(int j=i;j<n;j+=i<<1)
			{
				dat.back()[j-1]=dat[0][j-1];
				for(int k=2;k<=i;k++)
				{
					dat.back()[j-k]=calcfn(dat[0][j-k],dat.back()[j-k+1]);
				}
				dat.back()[j]=dat[0][j];
				for(int k=2;k<=i&&j+k<=n;k++)
				{
					dat.back()[j+k-1]=calcfn(dat[0][j+k-1],dat.back()[j+k-2]);
				}
			}
		}
	}
	T query(int l,int r)const//[l,r)
	{
		if(l<0)l=0;
		if(r>n)r=n;
		r--;
		if(l==r)return dat[0][l];
		int k=31-__builtin_clz(l^r);
		return calcfn(dat[k][l],dat[k][r]);
	}
};
int id[1<<17];
int rev[1<<20];
int len[1<<17];
main()
{
	int N;
	cin>>N;
	string s="";
	for(int i=0;i<N;i++)
	{
		string t;cin>>t;
		id[i]=s.size();
		len[i]=t.size();
		s+=t;
		s+='$';
	}
	SA P(s);
	for(int i=0;i<P.size();i++)rev[P[i]]=i;
	LCP Q(P);
	DST<int>X(Q.lcp);
	int M;
	long x,d;
	cin>>M>>x>>d;
	long ans=0;
	for(;M--;)
	{
		int i=x/(N-1),j=x%(N-1);
		if(i>j)i^=j^=i^=j;
		else j++;
		int I=rev[id[i]],J=rev[id[j]];
		if(I>J)I^=J^=I^=J;
		ans+=min(X.query(I,J),min(len[i],len[j]));
		x=(x+d)%((long)N*(N-1));
	}
	cout<<ans<<endl;
}
0