結果

問題 No.563 超高速一人かるた large
コンテスト
ユーザー koyumeishi
提出日時 2015-09-26 18:28:34
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,702 bytes
コンパイル時間 759 ms
コンパイル使用メモリ 71,848 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-01 20:00:14
合計ジャッジ時間 4,092 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

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

	vector<int> ans(n);
	for(int i=0; i<n; i++){
		int lb = 0;
		int ub = s[x[i]].size();

		while(ub-lb>1){
			int mid = (lb+ub)/2;
			int my_hash = lolita.get_hash(x[i], 0,mid);

			bool ok = true;
			for(int j=n-1; j>i; j--){
				int perv_hash = lolita.get_hash(x[j], 0,mid);
				if(perv_hash == my_hash){
					ok = false;
					break;
				}
			}
			if(ok){
				ub = mid;
			}else{
				lb = mid;
			}
		}

		ans[i] = ub;
	}

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




	return 0;
}
0