結果
問題 | No.515 典型LCP |
ユーザー | mamekin |
提出日時 | 2017-05-06 00:50:42 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 401 ms / 1,000 ms |
コード長 | 2,361 bytes |
コンパイル時間 | 1,081 ms |
コンパイル使用メモリ | 110,384 KB |
実行使用メモリ | 50,400 KB |
最終ジャッジ日時 | 2023-10-12 11:18:05 |
合計ジャッジ時間 | 5,970 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 391 ms
50,116 KB |
testcase_01 | AC | 401 ms
50,400 KB |
testcase_02 | AC | 273 ms
39,924 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 1 ms
4,352 KB |
testcase_05 | AC | 237 ms
40,312 KB |
testcase_06 | AC | 238 ms
40,188 KB |
testcase_07 | AC | 234 ms
40,220 KB |
testcase_08 | AC | 242 ms
40,424 KB |
testcase_09 | AC | 245 ms
40,832 KB |
testcase_10 | AC | 179 ms
40,704 KB |
testcase_11 | AC | 173 ms
40,644 KB |
testcase_12 | AC | 174 ms
40,664 KB |
testcase_13 | AC | 247 ms
40,176 KB |
testcase_14 | AC | 32 ms
17,336 KB |
testcase_15 | AC | 259 ms
40,164 KB |
testcase_16 | AC | 260 ms
40,044 KB |
ソースコード
#define _USE_MATH_DEFINES #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <complex> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> #include <iterator> using namespace std; class RollingHash { private: static const int X, M; vector<long long> xp; vector<long long> hash; public: RollingHash(const string& s){ int n = s.size(); xp.assign(n+1, 1); hash.assign(n+1, 0); for(int i=0; i<n; ++i){ hash[i+1] = hash[i]; hash[i+1] *= X; hash[i+1] += s[i]; hash[i+1] %= M; xp[i+1] = xp[i]; xp[i+1] *= X; xp[i+1] %= M; } } long long getHash(int a) const{ return hash[a+1]; } long long getHash(int a, int b) const{ long long ans = hash[b+1]; ans -= hash[a] * xp[b-a+1]; ans %= M; if(ans < 0) ans += M; return ans; } }; const int RollingHash::X = 1685440109; // 素数 const int RollingHash::M = 2000000087; // 合同式の法(素数) int solve(int len, const RollingHash& a, const RollingHash& b) { int left = 0; int right = len; while(left < right){ int mid = (left + right + 1) / 2; if(a.getHash(mid-1) != b.getHash(mid-1)) right = mid - 1; else left = mid; } return left; } int main() { int n; cin >> n; vector<string> s(n); for(int i=0; i<n; ++i) cin >> s[i]; vector<RollingHash> rh; for(int i=0; i<n; ++i) rh.push_back(RollingHash(s[i])); int m; long long x, d; cin >> m >> x >> d; vector<int> a(m), b(m); for(int i=0; i<m; ++i){ a[i] = (int)(x / (n - 1)); b[i] = (int)(x % (n - 1)); if(a[i] > b[i]) swap(a[i], b[i]); else ++ b[i]; x = (x + d) % (n * (n - 1LL)); } long long ans = 0; for(int i=0; i<m; ++i){ int len = min(s[a[i]].size(), s[b[i]].size()); ans += solve(len, rh[a[i]], rh[b[i]]); } cout << ans << endl; return 0; }