結果

問題 No.515 典型LCP
ユーザー tansunogontansunogon
提出日時 2017-05-07 04:17:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 3,598 bytes
コンパイル時間 1,678 ms
コンパイル使用メモリ 170,596 KB
実行使用メモリ 816,224 KB
最終ジャッジ日時 2024-09-14 14:15:21
合計ジャッジ時間 5,368 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other MLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct iostream_init_struct
{ 
	iostream_init_struct()
	{
		std::cin.tie(0);
		std::cin.sync_with_stdio(false);
	}
} iostream_init;

// thank you, tookunn
// http://tookunn.hatenablog.com/entry/2016/07/13/211148
class RMQ_SparseTable
{
public:
	// table[k][i] means minimum value in [i, i + 2^k)
	std::vector<std::vector<int>> table;

	RMQ_SparseTable(int* A, size_t N)
	{
		table = std::vector<std::vector<int>>(std::__lg(N) + 1, vector<int>(N));

		for (int i = 0; i < N; ++i)
		{
			table[0][i] = A[i];
		}

		for (int k = 1; (1 << k) <= N; k++)
		{
			for (int i = 0; i + (1 << k) <= N; ++i)
			{
				table[k][i] = min(table[k - 1][i], table[k - 1][i + (1 << (k - 1))]);
			}
		}
	}

	// returns min value in [s, t)
	inline int getMin(int s, int t)
	{
		int range = t - s;
		int k = std::__lg(range);

		int value1 = table[k][s];
		int value2 = table[k][t - (1 << k)];
		return min(value1, value2);
	}
};

int N;
string s[100000];
int si[100000];
int M;
long long x, d;
int i, j;

int index_table[100000];
int LCP_table[100000];

// same as pekempey's submission
// http://yukicoder.me/submissions/172137
int di, dj, ii, jj;
void next_init()
{
	di = d / (N - 1);
	dj = d % (N - 1);
	ii = x / (N - 1);
	jj = x % (N - 1);
	
	i = ii;
	j = jj;
	if (i <= j)
	{
		++j;
	}
}
inline void next()
{
	jj += dj;
	if (jj >= N - 1)
	{
		jj -= N - 1;
		++ii;
	}

	ii += di;
	if (ii >= N)
	{
		ii -= N;
	}

	i = ii;
	j = jj;
	if (i <= j)
	{
		++j;
	}
}


// multikey-quicksort
// http://d.hatena.ne.jp/echizen_tm/20100815/1281872393

// <- small
int si_temp_s[100000];
// <- middle ........ large ->
int si_temp_ml[100000];

// sort [l, r)
void multikey_qsort(int l, int r, int depth)
{
	char pivot = *(s[si[l]].data() + depth);
	int sorted = 0;
	int small = 0;
	int middle = 0;
	int large = 0;
	for (int ins_i = l; ins_i < r; ++ins_i)
	{
		int index = si[ins_i];
		char c = *(s[index].data() + depth);
		if (c == '\0')
		{
			si[l + sorted++] = index;
		}
		else if (c < pivot)
		{
			si_temp_s[small++] = index;
		}
		else if (c == pivot)
		{
			si_temp_ml[middle++] = index;
		}
		else
		{
			si_temp_ml[r - ++large] = index;
		}
	}
	memcpy(si + (l + sorted), si_temp_s, sizeof(int) * small);
	memcpy(si + (l + sorted + small), si_temp_ml, sizeof(int) * middle);
	memcpy(si + (l + sorted + small + middle), si_temp_ml + (r - large), sizeof(int) * large);
	multikey_qsort(l + sorted, l + sorted + small, depth);
	multikey_qsort(l + sorted + small, l + sorted + small + middle, depth + 1);
	multikey_qsort(l + sorted + small + middle, r, depth);
}
void multikey_qsort()
{
	multikey_qsort(0, N, 0);
}

int LCP(const char* s1, const char* s2, size_t min_length)
{
	int ret = 0;

	while (ret < min_length)
	{
		if (s1[ret] == s2[ret])
		{
			++ret;
		}
		else
		{
			break;
		}
	}

	return ret;
}

int main()
{
	// get input
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> s[i];
	}
	cin >> M >> x >> d;

	// sort
	for (int i = 0; i < N; ++i)
	{
		si[i] = i;
	}
	multikey_qsort();

	// reindex
	for (int i = 0; i < N; ++i)
	{
		index_table[si[i]] = i;
	}

	// calc LCP
	for (int i = 0; i < N - 1; ++i)
	{
		string& s1 = s[si[i]];
		string& s2 = s[si[i + 1]];
		LCP_table[i] = LCP(s1.c_str(), s2.c_str(), min(s1.size(), s2.size()));
	}

	// make Sparse Table
	RMQ_SparseTable sparse_table(LCP_table, N - 1);

	// calc ans
	long long sum = 0;
	next_init();
	for (int indx = 0; indx < M; ++indx)
	{
		int i_ = index_table[i];
		int j_ = index_table[j];
		if (i_ > j_)
			std::swap(i_, j_);
		sum += sparse_table.getMin(i_, j_);
		next();
	}

	cout << sum << endl;
}
0