結果

問題 No.515 典型LCP
ユーザー tansunogontansunogon
提出日時 2017-05-07 20:06:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 62 ms / 1,000 ms
コード長 7,181 bytes
コンパイル時間 759 ms
コンパイル使用メモリ 56,832 KB
実行使用メモリ 12,908 KB
最終ジャッジ日時 2024-09-14 14:50:57
合計ジャッジ時間 1,710 ms
ジャッジサーバーID
(参考情報)
judge3 / judge6
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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 = *(s[si[l]] + 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] + 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1