#172333 (C++14) No.515 典型LCP

• 問題: No.515 典型LCP
• ユーザー: tansunogon
• 提出日時: 2017-05-06 16:10:33
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 98 ms / 1,000 ms
• コード長: 4,214 bytes
• コンパイル時間: 2,419 ms
• コンパイル使用メモリ: 183,944 KB
• 実行使用メモリ: 14,592 KB
• 最終ジャッジ日時: 2024-09-14 13:55:23
• 合計ジャッジ時間: 3,715 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	98 ms; 14,592 KB
testcase_01	AC	92 ms; 14,464 KB
testcase_02	AC	42 ms; 7,424 KB
testcase_03	AC	5 ms; 6,656 KB
testcase_04	AC	5 ms; 6,528 KB
testcase_05	AC	22 ms; 7,424 KB
testcase_06	AC	22 ms; 7,424 KB
testcase_07	AC	21 ms; 7,424 KB
testcase_08	AC	32 ms; 7,424 KB
testcase_09	AC	24 ms; 7,424 KB
testcase_10	AC	23 ms; 7,296 KB
testcase_11	AC	24 ms; 7,168 KB
testcase_12	AC	24 ms; 7,296 KB
testcase_13	AC	23 ms; 7,424 KB
testcase_14	AC	8 ms; 7,424 KB
testcase_15	AC	22 ms; 7,424 KB
testcase_16	AC	21 ms; 7,424 KB

ソースコード

#pragma GCC optimize ("O3")
#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, tookunn
// http://tookunn.hatenablog.com/entry/2016/07/13/211148
#include <vector>
#include <algorithm>
#ifndef _WIN32
#include <bits/stdc++.h>
#endif
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>>(log(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 = log(range);

		int value1 = table[k][s];
		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;

#ifndef _WIN32
		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
	}
};

#include <string>
#include <algorithm>
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;
	}
}

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;
}

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

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

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

	// sort
	for (int i = 0; i < N; ++i)
	{
		si[i] = i;
	}
	sort(si, si + N,
		[&](int i, int j)
		{
			return s[i] < s[j];
		});
	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)
	{
		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()));
	}
	TimePrint("LCP  ");
	// make Sparse Table
	RMQ_SparseTable sparse_table(LCP_table, N - 1);
	TimePrint("SpTab");

	// 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();
	}
	TimePrint("clAns");

	cout << sum << endl;
}