結果

問題 No.515 典型LCP
ユーザー tansunogontansunogon
提出日時 2017-05-07 21:47:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 66 ms / 1,000 ms
コード長 7,247 bytes
コンパイル時間 536 ms
コンパイル使用メモリ 56,832 KB
実行使用メモリ 12,800 KB
最終ジャッジ日時 2024-09-14 14:52:15
合計ジャッジ時間 1,681 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
12,800 KB
testcase_01 AC 59 ms
12,800 KB
testcase_02 AC 24 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 12 ms
5,376 KB
testcase_06 AC 12 ms
5,376 KB
testcase_07 AC 12 ms
5,376 KB
testcase_08 AC 12 ms
5,376 KB
testcase_09 AC 17 ms
5,376 KB
testcase_10 AC 18 ms
5,376 KB
testcase_11 AC 18 ms
5,376 KB
testcase_12 AC 18 ms
5,376 KB
testcase_13 AC 18 ms
5,376 KB
testcase_14 AC 7 ms
6,144 KB
testcase_15 AC 12 ms
5,376 KB
testcase_16 AC 12 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

// 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)
	// simple code: std::vector<std::vector<int>> table;
	std::vector<int*> table;
	std::vector<int> table_data;

	RMQ_SparseTable(int* A, size_t N)
	{
		// init table (try to make a compact table)
		// simple code: table = std::vector<std::vector<int>>(log(N) + 1, vector<int>(N));
		size_t K_size = log(N) + 1;
		table = std::vector<int*>(K_size);
		table_data = std::vector<int>((N + 1) * K_size - (1 << K_size) + 1);
		for (int k = 0, allocated = 0; k < K_size; ++k)
		{
			table[k] = table_data.data() + allocated;
			allocated += N + 1 - (1 << k);
		}

		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 = log(range);

		int value1 = table[k][s];
		if (value1 == 0)
			return 0;

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

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

#ifdef __GNUC__
		return std::__lg(n);
#else
		if (n >= (1 << 16))
		{
			return 16;
		}
		else if (n >= (1 << 15))
		{
			return 15;
		}
		else if (n >= (1 << 14))
		{
			return 14;
		}
		else if (n >= (1 << 13))
		{
			return 13;
		}
		else if (n >= (1 << 12))
		{
			return 12;
		}
		else if (n >= (1 << 11))
		{
			return 11;
		}
		else if (n >= (1 << 10))
		{
			return 10;
		}
		else if (n >= (1 << 9))
		{
			return 9;
		}
		else if (n >= (1 << 8))
		{
			return 8;
		}
		else if (n >= (1 << 7))
		{
			return 7;
		}
		else if (n >= (1 << 6))
		{
			return 6;
		}
		else if (n >= (1 << 5))
		{
			return 5;
		}
		else if (n >= (1 << 4))
		{
			return 4;
		}
		else if (n >= (1 << 3))
		{
			return 3;
		}
		else if (n >= (1 << 2))
		{
			return 2;
		}
		else if (n >= (1 << 1))
		{
			return 1;
		}
		else
		{
			return 0;
		}
#endif
	}
};

int N;
char buf[1000000];
char* s[100000];
int s_len[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;
int di_N1, iii;
inline void init_ij()
{
	di = d / (N - 1);
	dj = d % (N - 1);
	ii = x / (N - 1);
	jj = x % (N - 1);

	di_N1 = d % N;

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

	iii = ii;
}
inline void next_ij()
{
	jj += dj;
	if (jj >= N - 1)
	{
		jj -= N - 1;
		++ii;
	}

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

	i = ii;
	if (ii > jj)
	{
		j = jj;
	}
	else
	{
		j = jj + 1;
	}

	iii = ii;
}
// If you go to the next-(N - 1) step, you can get the same j
inline void next_Nminus1_ij()
{
	iii += di_N1;
	if (iii >= N)
	{
		iii -= N;
	}

	i = iii;
	if (iii > jj)
	{
		j = jj;
	}
	else
	{
		j = jj + 1;
	}
}


// multikey-quicksort (faster than std::sort() when you sort strings)
// 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)
{
	if (r - l < 2)
	{
		//// insertion sort
		//si[l] = si[l];
		//for (int ins_i = l + 1; ins_i < r; ++ins_i)
		//{
		//	int ins_v = si[ins_i];
		//	int i = 0;
		//	for (; i < ins_i; ++i)
		//	{
		//		if (strcmp(s[si[i]] + depth, s[ins_v] + depth) > 0)
		//		{
		//			for (int j = ins_i; j > i; --j)
		//			{
		//				si[j] = si[j - 1];
		//			}
		//			si[i] = ins_v;
		//			break;
		//		}
		//	}
		//	if (i == ins_i)
		//	{
		//		si[ins_i] = ins_v;
		//	}
		//}
		//return;
	}
	else
	{
		char pivot = ((unsigned char)(*(s[si[l]] + depth)) + (unsigned char)(*(s[si[r - 1]] + depth))) / 2;
		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] + depth);
			if (c == '\n')
			{
				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;

	// not useful for the test case: "challenge01.txt"
	//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;
}

#ifdef _WIN32
#include <iostream>
#include <windows.h>
DWORD time = GetTickCount();
#define TimePrint(x) do { cout << x " " << GetTickCount() - time << endl; time = GetTickCount(); } while (false)
#else
#define TimePrint(x) do {} while (false)
#endif

int main()
{
	TimePrint("(start)");

	// get input
	fread(buf, sizeof(char), sizeof(buf), stdin);
	{
		char* p = buf;

		// N
		N = 0;
		while (*p != '\n')
			N = 10 * N + (int)(*p++ - '0');
		++p;

		// strings
		for (int i = 0; i < N; ++i)
		{
			s[i] = p;
			while (*++p != '\n') {}
			s_len[i] = p - s[i];
			++p;
		}

		// M
		M = 0;
		while (*p != ' ')
			M = 10 * M + (int)(*p++ - '0');
		++p;

		// x
		x = 0;
		while (*p != ' ')
			x = 10 * x + (int)(*p++ - '0');
		++p;

		// d
		d = 0;
		while (*p != '\n')
			d = 10 * d + (int)(*p++ - '0');
	}
	TimePrint("input");

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

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

	// calc LCP
	for (int i = 0; i < N - 1; ++i)
	{
		char* s1 = s[si[i]];
		int s1_len = s_len[si[i]];
		char* s2 = s[si[i + 1]];
		int s2_len = s_len[si[i + 1]];
		LCP_table[i] = LCP(s1, s2, min(s1_len, s2_len));
	}
	TimePrint("LCP  ");

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

	// calc ans
	long long sum = 0;
	init_ij();
	for (int small_step = 0; small_step < N - 1; ++small_step)
	{
		int num_steps = M / (N - 1) + (M - M / (N - 1) * (N - 1) > small_step);
		for (int large_step = 0; large_step < num_steps; ++large_step)
		{
			int i_ = index_table[i];
			int j_ = index_table[j];
			if (i_ > j_)
				std::swap(i_, j_);
			sum += sparse_table.getMin(i_, j_);

			next_Nminus1_ij();
		}
		next_ij();
	}
	TimePrint("clAns");

	printf("%lld", sum);
}
0