結果

問題 No.515 典型LCP
ユーザー pekempeypekempey
提出日時 2017-05-05 22:59:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,002 bytes
コンパイル時間 1,469 ms
コンパイル使用メモリ 89,560 KB
実行使用メモリ 106,996 KB
最終ジャッジ日時 2024-09-14 09:56:22
合計ジャッジ時間 6,712 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 245 ms
85,584 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 325 ms
99,680 KB
testcase_06 AC 335 ms
93,272 KB
testcase_07 AC 325 ms
96,504 KB
testcase_08 AC 351 ms
99,552 KB
testcase_09 AC 183 ms
89,232 KB
testcase_10 AC 181 ms
86,280 KB
testcase_11 AC 186 ms
86,272 KB
testcase_12 AC 186 ms
86,272 KB
testcase_13 AC 185 ms
88,756 KB
testcase_14 AC 119 ms
88,692 KB
testcase_15 AC 309 ms
96,056 KB
testcase_16 AC 319 ms
94,844 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

using namespace std;

vector<int> sufarray(vector<int> a) {
	const int TYPE_S = -1;
	const int TYPE_L = -2;
	int n = a.size();
	if (n == 1) {
		return vector<int>(1);
	}
	vector<int> type(n);
	type.back() = TYPE_S;
	for (int i = n - 2; i >= 0; i--) {
		if (a[i] < a[i + 1]) {
			type[i] = TYPE_S;
		} else if (a[i] > a[i + 1]) {
			type[i] = TYPE_L;
		} else {
			type[i] = type[i + 1];
		}
	}
	vector<int> lmsID;
	vector<vector<int>> lms;
	int prev = n;
	for (int i = n - 1; i >= 1; i--) {
		if (type[i - 1] == TYPE_L && type[i] == TYPE_S) {
			type[i] = lmsID.size();
			lmsID.push_back(i);
			lms.emplace_back(vector<int>(a.begin() + i, a.begin() + prev));
			prev = i;
		}
	}
	auto inducedSort = [&](vector<int> &a, vector<int> &ordSS, vector<int> &type) {
		int n = a.size();
		vector<int> sa(n, -1);
		int maxi = *max_element(a.begin(), a.end());
		vector<int> L(maxi + 2), S(maxi + 2);
		for (int i = 0; i < n; i++) {
			L[a[i] + 1]++;
		}
		for (int i = 0; i < L.size() - 1; i++) {
			L[i + 1] += L[i];
			S[i] = L[i + 1];
		}
		for (int i = ordSS.size() - 1; i >= 0; i--) {
			int j = ordSS[i];
			sa[--S[a[j]]] = j;
		}
		for (int i = 0; i < L.size() - 1; i++) {
			S[i] = L[i + 1];
		}
		for (int i = 0; i < n; i++) {
			int j = sa[i] - 1;
			if (j >= 0 && type[j] == TYPE_L) {
				sa[L[a[j]]++] = j;
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			int j = sa[i] - 1;
			if (j >= 0 && (type[j] == TYPE_S || type[j] >= 0)) {
				sa[--S[a[j]]] = j;
			}
		}
		return sa;
	};
	int SS = lmsID.size();
	vector<int> ordLms;
	for (int i : inducedSort(a, lmsID, type)) {
		if (type[i] >= 0) {
			ordLms.push_back(i);
		}
	}
	reverse(lmsID.begin(), lmsID.end());
	vector<int> rankLms(SS);
	for (int i = 1; i < SS; i++) {
		int x = type[ordLms[i - 1]];
		int y = type[ordLms[i]];
		rankLms[i] = rankLms[i - 1] + (lms[x] < lms[y]);
	}
	for (int i = 0; i < SS; i++) {
		type[ordLms[i]] = rankLms[i];
	}
	vector<int> lmsA;
	for (int i : lmsID) {
		lmsA.push_back(type[i]);
	}
	vector<int> ordSS;
	for (int i : sufarray(lmsA)) {
		ordSS.push_back(lmsID[i]);
	}
	return inducedSort(a, ordSS, type);
}

vector<int> lcparray(const vector<int> &s, const vector<int> &sa) {
	const int n = s.size() - 1;
	vector<int> isa(n + 1), lcp(n + 1);
	for (int i = 0; i <= n; i++) {
		isa[sa[i]] = i;
	}
	int k = 0;
	for (int i = 0; i < n; i++) {
		int j = sa[isa[i] - 1];
		k = max(0, k - 1);
		while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
		lcp[isa[i] - 1] = k;
	}
	return lcp;
}

struct RMQ {
	vector<int> lg;
	vector<vector<int>> dat;

	RMQ(const vector<int> &a) {
		const int n = a.size();
		lg.resize(n + 1);
		for (int i = 2; i <= n; i++) {
			lg[i] = lg[i / 2] + 1;
		}
		const int m = lg[n];
		dat.assign(m + 1, vector<int>(n));
		for (int i = 0; i < n; i++) {
			dat[0][i] = a[i];
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j + (1 << i) < n; j++) {
				dat[i + 1][j] = min(dat[i][j], dat[i][j + (1 << i)]);
			}
		}
	}

	int getmin(int l, int r) {
		int k = lg[r - l];
		return min(dat[k][l], dat[k][r - (1 << k)]);
	}
};

int main() {
	int n;
	cin >> n;

	vector<string> s(n);
	vector<int> start(n);
	vector<int> t;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		start[i] = t.size();
		for (char c : s[i]) {
			t.push_back(c);
		}
		t.push_back(i + 'z' + 1);
	}
	t.push_back(0);

	auto sa = sufarray(t);
	auto lcp = lcparray(t, sa);

	vector<int> isa(t.size());
	for (int i = 0; i < t.size(); i++) {
		isa[sa[i]] = i;
	}

	RMQ rmq(lcp);

	int m, x, d;
	cin >> m >> x >> d;

	long long ans = 0;
	for (int k = 0; k < m; k++) {
		int i = (x / (n - 1)) + 1;
		int j = (x % (n - 1)) + 1;
		if (i > j) {
			swap(i, j);
		} else {
			j = j + 1;
		}
		x = (x + d) % (1LL * n * (n - 1));
		i--;
		j--;
		if (isa[start[i]] > isa[start[j]]) {
			swap(i, j);
		}
		if (i == j) {
			ans += s[i].size();
		} else {
			ans += rmq.getmin(isa[start[i]], isa[start[j]]);
		}
	}
	cout << ans << endl;
}
0