結果
問題 | No.515 典型LCP |
ユーザー |
|
提出日時 | 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 |
ソースコード
#include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;// thank you, tookunn// http://tookunn.hatenablog.com/entry/2016/07/13/211148class 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);#elseif (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/172137int 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 jinline 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// <- smallint 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)#endifint main(){TimePrint("(start)");// get inputfread(buf, sizeof(char), sizeof(buf), stdin);{char* p = buf;// NN = 0;while (*p != '\n')N = 10 * N + (int)(*p++ - '0');++p;// stringsfor (int i = 0; i < N; ++i){s[i] = p;while (*++p != '\n') {}s_len[i] = p - s[i];++p;}// MM = 0;while (*p != ' ')M = 10 * M + (int)(*p++ - '0');++p;// xx = 0;while (*p != ' ')x = 10 * x + (int)(*p++ - '0');++p;// dd = 0;while (*p != '\n')d = 10 * d + (int)(*p++ - '0');}TimePrint("input");// sortfor (int i = 0; i < N; ++i){si[i] = i;}multikey_qsort();TimePrint("sort ");// reindexfor (int i = 0; i < N; ++i){index_table[si[i]] = i;}TimePrint("reidx");// calc LCPfor (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 TableRMQ_SparseTable sparse_table(LCP_table, N - 1);TimePrint("SpTab");// calc anslong 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);}