結果

問題 No.563 超高速一人かるた large
ユーザー koyumeishikoyumeishi
提出日時 2015-09-26 17:59:17
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,690 bytes
コンパイル時間 817 ms
コンパイル使用メモリ 71,760 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-09 19:46:33
合計ジャッジ時間 3,048 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 RE -
testcase_04 RE -
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 -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
権限があれば一括ダウンロードができます

ソースコード

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;
				}
			}
			if(ok){
				ub = mid;
			}else{
				lb = mid;
			}
		}

		ans[i] = ub;
	}

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




	return 0;
}
0