結果

問題 No.563 超高速一人かるた large
ユーザー koyumeishikoyumeishi
提出日時 2015-09-28 17:51:06
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,202 bytes
コンパイル時間 1,052 ms
コンパイル使用メモリ 89,288 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-09 19:46:44
合計ジャッジ時間 1,910 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 13 ms
6,940 KB
testcase_20 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>

using namespace std;

class Rolling_Hash{
public:
	int N;
	vector<int> p_pow;
	const int P;
	const int MOD;

	vector<vector<int>> hash;

	Rolling_Hash(const int n) : 
		P(vector<int>{10009, 10007}[0/*rand()%2*/]),
		MOD(vector<int>{1000000007, 1000000009}[0/*rand()%2*/]),
		N(n),
		p_pow(n+1)
	{
		p_pow[0] = 1;
		for(int i=1; i<=N; i++){
			p_pow[i] = (1LL * p_pow[i-1] * P) % MOD;
		}
	}

	// [l,r)
	long long get_hash(int at, int l, int r){
		if(r>=hash[at].size()) return -at;
		int len = r-l;
		return (hash[at][r] - (1LL * hash[at][l]* p_pow[len])%MOD + MOD) % MOD;
	}

	void insert(const string& s){
		//hash[i] = [0,i)
		hash.push_back({});
		hash.back().resize(s.size()+1);
		int at = hash.size() - 1;
		for(int i=0; i<s.size(); i++){
			hash[at][i+1] = (1LL * hash[at][i] * P + s[i])%MOD;
		}
	}

};

int lcp(Rolling_Hash& hash, vector<string>& s, int x, int y){
	int lb = 0;
	int ub = s[x].size();

	while(ub-lb>1){
		int mid = (lb+ub)/2;
		int hash_x = hash.get_hash(x, 0,mid);
		int hash_y = hash.get_hash(y, 0,mid);

		bool ok = hash_x != hash_y;

		if(ok){
			ub = mid;
		}else{
			lb = mid;
		}
	}

	return ub;
}

int main(){
	int n;
	cin >> n;
	vector<string> s(n);
	int m = 0;
	for(int i=0; i<n; i++){
		cin >> s[i];
		s[i] += 'a'-1;
		m = max(m, (int)s[i].size());
	}
	vector<int> x(n);
	for(int i=0; i<n; i++){
		cin >> x[i];
		x[i]--;
	}

	vector<pair<string, int>> v(n);
	for(int i=0; i<n; i++){
		v[i] = {s[i], i};
	}
	sort(v.begin(), v.end());

	vector<int> index(n);
	vector<int> order(n);
	for(int i=0; i<n; i++){
		index[i] = v[i].second;
		order[v[i].second] = i;
	}

	set<int> w;

	Rolling_Hash hash(m);
	for(int i=0; i<n; i++){
		hash.insert(s[i]);
	}

	vector<int> ans(n);

	for(int i=n-1; i>=0; i--){
		auto itr = w.insert(order[x[i]]).first;
		int lcp_len = 1;
		if(itr != w.begin()){
			itr--;
			lcp_len = max(lcp_len, lcp(hash,s, x[i], index[*itr]));
			itr++;
		}
		itr++;
		if(itr != w.end()){
			lcp_len = max(lcp_len, lcp(hash,s, x[i], index[*itr]));
		}
		ans[i] = lcp_len;
	}

	for(int i=0; i<n; i++){
		cout << ans[i] << endl;
	}




	return 0;
}
0