結果

問題 No.515 典型LCP
ユーザー tansunogontansunogon
提出日時 2017-05-06 04:36:52
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 245 ms / 1,000 ms
コード長 2,935 bytes
コンパイル時間 1,185 ms
コンパイル使用メモリ 85,684 KB
実行使用メモリ 14,940 KB
最終ジャッジ日時 2024-09-14 12:31:32
合計ジャッジ時間 3,861 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 230 ms
14,940 KB
testcase_01 AC 245 ms
14,812 KB
testcase_02 AC 130 ms
8,428 KB
testcase_03 AC 5 ms
7,212 KB
testcase_04 AC 3 ms
7,296 KB
testcase_05 AC 91 ms
8,236 KB
testcase_06 AC 93 ms
8,064 KB
testcase_07 AC 92 ms
8,192 KB
testcase_08 AC 114 ms
8,064 KB
testcase_09 AC 96 ms
8,188 KB
testcase_10 AC 98 ms
8,064 KB
testcase_11 AC 98 ms
8,064 KB
testcase_12 AC 98 ms
8,064 KB
testcase_13 AC 92 ms
8,184 KB
testcase_14 AC 8 ms
8,068 KB
testcase_15 AC 87 ms
8,064 KB
testcase_16 AC 85 ms
8,112 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using namespace std;

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

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

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

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

		for (int k = 1; (1 << k) <= N; k++)
		{
			for (int i = 0; i + (1 << k) <= N; ++i)
			{
				int first = table[k - 1][i];
				int second = table[k - 1][i + (1 << (k - 1))];
				if (A[first] < A[second])
				{
					table[k][i] = first;
				}
				else
				{
					table[k][i] = second;
				}
			}
		}
	}

	// returns min value in [s, t)
	int getMin(int s, int t)
	{
		int range = t - s;
		int k = log(range);

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

	static int log(int n)
	{
		int ret = 0;
		while (n = n >> 1)
		{
			ret += 1;
		}
		return ret;
	}
};

#include <string>
#include <algorithm>
int N;
pair<string, int> s[100000];
int M;
long long x, d;
int i, j;

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

void next()
{
	i = (x / (N - 1));
	j = (x % (N - 1));
	if (i > j)
	{
		//int temp = i;
		//i = j;
		//j = temp;
	}
	else
	{
		j = j + 1;
	}
	x = (x + d) % ((long long)(N) * (N - 1));
}

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

	const uint64_t* s64i = reinterpret_cast<const uint64_t*>(s1);
	const uint64_t* s64j = reinterpret_cast<const uint64_t*>(s2);
	while (ret < min_length / 8)
	{
		if (s64i[ret] == s64j[ret])
		{
			++ret;
		}
		else
		{
			break;
		}
	}
	ret *= 8;

	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].first;
		s[i].second = i;
	}
	cin >> M >> x >> d;

	// sort
	sort(s, s + N);
	// reindex
	for (int i = 0; i < N; ++i)
	{
		index_table[s[i].second] = i;
	}
	// calc LCP
	for (int i = 0; i < N - 1; ++i)
	{
		string& s1 = s[i].first;
		string& s2 = s[i + 1].first;
		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;
	for (int indx = 0; indx < M; ++indx)
	{
		next();
		int smaller_index, bigger_index;
		if (index_table[i] < index_table[j])
		{
			smaller_index = index_table[i];
			bigger_index  = index_table[j];
		}
		else
		{
			smaller_index = index_table[j];
			bigger_index  = index_table[i];
		}
		sum += sparse_table.getMin(smaller_index, bigger_index);
	}

	cout << sum << endl;
}
0