結果
問題 | No.515 典型LCP |
ユーザー | coindarw |
提出日時 | 2023-04-26 22:31:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 11,613 bytes |
コンパイル時間 | 4,808 ms |
コンパイル使用メモリ | 273,180 KB |
実行使用メモリ | 32,200 KB |
最終ジャッジ日時 | 2024-04-27 23:10:22 |
合計ジャッジ時間 | 18,359 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | TLE | - |
testcase_02 | AC | 759 ms
21,724 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 785 ms
31,700 KB |
testcase_06 | TLE | - |
testcase_07 | AC | 912 ms
32,008 KB |
testcase_08 | TLE | - |
testcase_09 | AC | 579 ms
21,688 KB |
testcase_10 | AC | 695 ms
21,680 KB |
testcase_11 | AC | 682 ms
21,776 KB |
testcase_12 | AC | 695 ms
21,732 KB |
testcase_13 | AC | 560 ms
21,748 KB |
testcase_14 | AC | 51 ms
21,684 KB |
testcase_15 | AC | 712 ms
31,376 KB |
testcase_16 | AC | 686 ms
31,356 KB |
ソースコード
// #include <bits/stdc++.h> // using ll = long long; // #define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) // #define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) // #define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i) // #define rreps(i, n) for (int i = ((int)(n)); i > 0; --i) // #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) // #define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++) // #define bitrep(i, n) for (int i = 0, i##_len = (1 << (int)(n)); i < i##_len; i++) // #define bitrrep(i, n) for (int i = (1 << (int)(n)) - 1ll; i >= 0; i--) // constexpr int inf = 2000'000'000; // constexpr ll linf = 4000000000000000000ll; // constexpr ll M7 = 1000000007ll; // constexpr ll M09 = 1000000009ll; // constexpr ll M9 = 998244353ll; // #define all(v) begin(v), end(v) // #define rall(v) rbegin(v), rend(v) // using namespace std; // template <typename T> // inline ostream& operator<<(ostream& os, vector<T>& v) { // for (auto& e : v) os << e << " "; // return os; // } // template <typename T, typename U> // std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) noexcept { // return os << "(" << p.first << ", " << p.second << ")"; // } #include <bits/stdc++.h> #include <atcoder/all> using ll = long long; #define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) #define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) #define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i) #define rreps(i, n) for (int i = ((int)(n)); i > 0; --i) #define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i) #define repc2(i, s, n) for (int i = (s); i <= (int)(n); ++i) constexpr int inf = 2000'000'000; constexpr ll linf = 4000000000000000000ll; constexpr ll M7 = 1000000007ll; constexpr ll M09 = 1000000009ll; constexpr ll M9 = 998244353ll; #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) using namespace std; using namespace atcoder; template <typename T> inline ostream& operator<<(ostream& os, vector<T>& v) { for (auto& e : v) os << e << " "; return os; } template <typename T, typename U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) noexcept { return os << "(" << p.first << ", " << p.second << ")"; } #ifdef ONLINE_JUDGE #define debug(...) #else #define debug(...) cerr << "<" << #__VA_ARGS__ << ">: ", debug_out(__VA_ARGS__) template <typename T> void debug_out(T t) { cerr << t << endl; } template <typename T, typename... Args> void debug_out(T t, Args... args) { cerr << t << ", "; debug_out(args...); } #endif class StrAlgos { private: public: static vector<int> sa_is(vector<int> v, int upper) { // 1 <= v[i] <= upper if (v.size() == 0) return {}; else if (v.size() == 1) return {0}; else if (v.size() == 2) if (v[0] < v[1]) return {0, 1}; else return {1, 0}; constexpr int TERM = 0; v.emplace_back(TERM); const int n = v.size(); vector<int> bl(upper + 1), br(upper + 1); // bucket range for (int i = 0; i < n; ++i) br[v[i]]++; for (int i = 1; i <= upper; ++i) br[i] += br[i - 1]; for (int i = 1; i <= upper; ++i) bl[i] = br[i - 1]; vector<bool> is_l(n); vector<int> lms, sa(n, -1), lms_ord(n); // lms_ord[i] := 0 -> not lms, 1~ -> 1-indexed for (int i = n - 2; i >= 0; --i) is_l[i] = (v[i] == v[i + 1]) ? is_l[i + 1] : (v[i] > v[i + 1]); for (int i = 1; i < n; ++i) { if (!is_l[i] && is_l[i - 1]) { sa[--br[v[i]]] = i; lms_ord[i] = ~int(lms.size()); lms.emplace_back(i); } } for (int i = 0; i < upper; ++i) br[i] = bl[i + 1]; br[upper] = n; for (int i = 0; i < n; ++i) if (sa[i] > 0 && is_l[sa[i] - 1]) sa[bl[v[sa[i] - 1]]++] = sa[i] - 1; for (int i = 1; i <= upper; ++i) bl[i] = br[i - 1]; for (int i = 1; i < n; i++) if (sa[i] > -1 && !is_l[sa[i]]) sa[i] = -1; for (int i = n - 1; i >= 1; i--) if (sa[i] > 0 && !is_l[sa[i] - 1]) sa[--br[v[sa[i] - 1]]] = sa[i] - 1; for (int i = 0; i < upper; ++i) br[i] = bl[i + 1]; br[upper] = n; vector<int> lms_substr_sorted(lms.size()); int cnt = 0; for (int i = 0; i < n; ++i) if (sa[i] > -1 && lms_ord[sa[i]]) lms_substr_sorted[cnt++] = sa[i]; // same lms_substr -> same rank auto same = [&](int l1, int l2) { if (l1 > l2) swap(l1, l2); if (l2 == n - 1) return false; int p1 = l1, p2 = l2; while (p1 <= lms[~lms_ord[l1] + 1] && p2 < n) if (v[p1] == v[p2]) ++p1, ++p2; else return false; return true; }; vector<int> ord(lms.size()); ord[0] = 1; for (int i = 0; i < lms.size() - 1; ++i) ord[i + 1] = same(lms_substr_sorted[i], lms_substr_sorted[i + 1]) ? ord[i] : (ord[i] + 1); vector<int> va(lms.size()); // make array of appearance order for (int i = 0; i < lms.size(); ++i) va[~lms_ord[lms_substr_sorted[i]]] = ord[i]; auto lms_sorted = sa_is(va, ord.back()); // place lms at correct position fill(all(sa), -1); for (int i = lms.size() - 1; i >= 0; i--) sa[--br[v[lms[lms_sorted[i]]]]] = lms[lms_sorted[i]]; for (int i = 0; i < upper; ++i) br[i] = bl[i + 1]; br[upper] = n; for (int i = 0; i < n; ++i) if (sa[i] > 0 && is_l[sa[i] - 1]) sa[bl[v[sa[i] - 1]]++] = sa[i] - 1; for (int i = 1; i < n; i++) if (sa[i] > -1 && !is_l[sa[i]]) sa[i] = -1; for (int i = n - 1; i >= 1; i--) if (sa[i] > 0 && !is_l[sa[i] - 1]) sa[--br[v[sa[i] - 1]]] = sa[i] - 1; sa.erase(sa.begin()); return sa; } static vector<int> sa_is(vector<int> v) { auto cv = v; sort(all(cv)); cv.erase(unique(all(cv)), cv.end()); for (auto& e : v) e = lower_bound(all(cv), e) - cv.begin(); return sa_is(v, cv.size() - 1); } static vector<int> sa_is(string s) { vector<int> v(s.size()); for (int i = 0; i < s.size(); i++) v[i] = s[i]; return sa_is(v, 255); } static vector<int> lcp(const string& s, const vector<int>& sa) { assert(sa.size() == s.size()); vector<int> rank(s.size()), _lcp(s.size() - 1); const int n = s.size(); for (int i = 0; i < n; i++) rank[sa[i]] = i; int h = 0; for (int i = 0; i < n; i++) { if (rank[i] == 0) continue; int j = sa[rank[i] - 1]; if (h > 0) h--; for (; j + h < n && i + h < n; h++) if (s[j + h] != s[i + h]) break; _lcp[rank[i] - 1] = h; } return _lcp; } static vector<int> lcp(const vector<int>& s, const vector<int>& sa) { assert(sa.size() == s.size()); const int n = s.size(); vector<int> rank(n), _lcp(n - 1); for (int i = 0; i < n; i++) rank[sa[i]] = i; int h = 0; for (int i = 0; i < n; i++) { if (rank[i] == 0) continue; int j = sa[rank[i] - 1]; if (h > 0) h--; for (; j + h < n && i + h < n; h++) if (s[j + h] != s[i + h]) break; _lcp[rank[i] - 1] = h; } return _lcp; } static vector<int> z_algo(string s) { int n = s.size(); vector<int> v(n); v[0] = n; int l = -1, r = -1; reps(i, n - 1) { if (l != -1) v[i] = max(min(v[i - l], int(r - i)), 0); while (i + v[i] < n && s[v[i]] == s[i + v[i]]) v[i]++; if (i + v[i] > r) { l = i; r = i + v[i]; } } return v; } static vector<int> z_algo(vector<int> v) { int n = v.size(); vector<int> res(n); res[0] = n; int l = -1, r = -1; reps(i, n - 1) { if (l != -1) res[i] = max(0, min(int(r - i), res[i - l])); while (i + res[i] < n && v[res[i]] == v[i + res[i]]) res[i]++; if (i + res[i] > r) { l = i; r = i + res[i]; } } return res; } }; template <typename T, T (*op)(T, T), T (*e)()> class SegTree { private: int n, _n; std::vector<T> dat; T _query(int a, int b, int p, int l, int r) { if (a >= r || b <= l) { return e(); } else if (a <= l && r <= b) { return dat.at(p); } int mid = (l + r) / 2; return op(_query(a, b, p * 2 + 1, l, mid), _query(a, b, p * 2 + 2, mid, r)); } public: SegTree(int n) : SegTree(std::vector<T>(n, e())) {} SegTree(const std::vector<T>& v) : _n(int(v.size())) { this->n = 1; while (this->n < _n) { this->n *= 2; } dat = std::vector<T>(2 * this->n - 1); for (int i = 0; i < _n; i++) { dat.at(i + n - 1) = v.at(i); } for (int i = n - 2; i >= 0; i--) { dat.at(i) = op(dat.at(i * 2 + 1), dat.at(i * 2 + 2)); } } T query(int l, int r) { assert(0 <= l && l < r && r <= _n); if (l == r) return e(); return _query(l, r, 0, 0, n); } void set(int p, T a) { assert(0 <= p && p < _n); p += n - 1; dat.at(p) = a; while (p > 0) { p = (p - 1) / 2; dat.at(p) = op(dat.at(p * 2 + 1), dat.at(p * 2 + 2)); } } T get(int p) { assert(0 <= p && p < _n); return dat.at(p + n - 1); } void print() { int lf = 0; rep(i, 2 * n - 1) { // cerr << "(" << dat[i].first.first << ", " << dat[i].first.second << ", " // << dat[i].second << ")\t"; cerr << "(" << dat[i] << ")\t"; if (i == lf) { lf = lf * 2 + 2; cerr << endl; } } } }; int e() { return inf; } int op(int a, int b) { return min(a, b); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> a(n); string s; int sum = 0; rep(i, n) { string t; cin >> t; a[i] = sum; sum += t.size(); s += t; } a.push_back(sum); auto sa = StrAlgos::sa_is(s); auto lcp = StrAlgos::lcp(s, sa); SegTree<int, op, e> st(lcp); vector<int> rev(n); rep(i, sum) { auto lb = lower_bound(all(a), sa[i]); if (lb != a.end() && *lb == sa[i]) rev.at(lb - a.begin()) = i; } ll m, x, d; cin >> m >> x >> d; ll ans = 0; reps(k, m) { ll i = (x / (n - 1)) + 1; ll j = (x % (n - 1)) + 1; if (i > j) swap(i, j); else j++; int _i = rev[i - 1], _j = rev[j - 1]; if (_i > _j) swap(_i, _j); ll r = min({st.query(_i, _j), a[i] - a[i - 1], a[j] - a[j - 1]}); ans += r; x = (x + d) % (n * (n - 1)); } cout << ans << "\n"; return 0; }