結果

問題 No.515 典型LCP
ユーザー coindarwcoindarw
提出日時 2023-04-26 23:45:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 457 ms / 1,000 ms
コード長 9,644 bytes
コンパイル時間 4,013 ms
コンパイル使用メモリ 273,432 KB
実行使用メモリ 83,492 KB
最終ジャッジ日時 2024-04-28 00:08:47
合計ジャッジ時間 9,063 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 457 ms
81,332 KB
testcase_01 AC 367 ms
80,824 KB
testcase_02 AC 247 ms
76,024 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 270 ms
80,948 KB
testcase_06 AC 272 ms
80,936 KB
testcase_07 AC 270 ms
80,940 KB
testcase_08 AC 283 ms
80,920 KB
testcase_09 AC 205 ms
75,988 KB
testcase_10 AC 189 ms
75,960 KB
testcase_11 AC 189 ms
75,868 KB
testcase_12 AC 188 ms
75,996 KB
testcase_13 AC 188 ms
76,104 KB
testcase_14 AC 97 ms
76,124 KB
testcase_15 AC 252 ms
83,492 KB
testcase_16 AC 261 ms
81,016 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 <class S, S (*op)(S, S), S (*e)()>
class DST {
    // https://noshi91.hatenablog.com/entry/2023/04/07/165310
    vector<vector<S>> t;
    int size() const { return t[0].size() - 2; }

   public:
    DST(const vector<S>& v) : t() {
        const int n = v.size() + 2, h = 32 - __builtin_clz(n - 1);
        t.assign(h, vector<S>(n, e()));
        for (int k = 1; k < h; k++) {
            auto& s = t[k];
            const int w = 1 << k;
            for (int i = w; i < n; i += w * 2) {
                for (int j = i - 1; j > i - w; j--) s[j - 1] = op(v[j - 1], s[j]);
                const int m = min(i + w - 1, n - 1);
                for (int j = i; j < m; j++) s[j + 1] = op(s[j], v[j - 1]);
            }
        }
    }
    S get(int p) const {
        assert(0 <= p && p < size());
        return prod(p, p + 1);
    }
    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= size());
        r++;
        const auto& s = t[31 - __builtin_clz(l ^ r)];
        return op(s[l], s[r]);
    }
};

int op(int a, int b) {
    return min(a, b);
}
int e() {
    return inf;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll 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;
    }
    auto sa = StrAlgos::sa_is(s);
    auto lcp = StrAlgos::lcp(s, sa);
    DST<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;
    }
    a.push_back(sum);

    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.prod(_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;
}
0