結果

問題 No.515 典型LCP
ユーザー pekempey
提出日時 2017-05-05 22:59:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,002 bytes
コンパイル時間 1,469 ms
コンパイル使用メモリ 89,560 KB
実行使用メモリ 106,996 KB
最終ジャッジ日時 2024-09-14 09:56:22
合計ジャッジ時間 6,712 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
using namespace std;
vector<int> sufarray(vector<int> a) {
    const int TYPE_S = -1;
    const int TYPE_L = -2;
    int n = a.size();
    if (n == 1) {
        return vector<int>(1);
    }
    vector<int> type(n);
    type.back() = TYPE_S;
    for (int i = n - 2; i >= 0; i--) {
        if (a[i] < a[i + 1]) {
            type[i] = TYPE_S;
        } else if (a[i] > a[i + 1]) {
            type[i] = TYPE_L;
        } else {
            type[i] = type[i + 1];
        }
    }
    vector<int> lmsID;
    vector<vector<int>> lms;
    int prev = n;
    for (int i = n - 1; i >= 1; i--) {
        if (type[i - 1] == TYPE_L && type[i] == TYPE_S) {
            type[i] = lmsID.size();
            lmsID.push_back(i);
            lms.emplace_back(vector<int>(a.begin() + i, a.begin() + prev));
            prev = i;
        }
    }
    auto inducedSort = [&](vector<int> &a, vector<int> &ordSS, vector<int> &type) {
        int n = a.size();
        vector<int> sa(n, -1);
        int maxi = *max_element(a.begin(), a.end());
        vector<int> L(maxi + 2), S(maxi + 2);
        for (int i = 0; i < n; i++) {
            L[a[i] + 1]++;
        }
        for (int i = 0; i < L.size() - 1; i++) {
            L[i + 1] += L[i];
            S[i] = L[i + 1];
        }
        for (int i = ordSS.size() - 1; i >= 0; i--) {
            int j = ordSS[i];
            sa[--S[a[j]]] = j;
        }
        for (int i = 0; i < L.size() - 1; i++) {
            S[i] = L[i + 1];
        }
        for (int i = 0; i < n; i++) {
            int j = sa[i] - 1;
            if (j >= 0 && type[j] == TYPE_L) {
                sa[L[a[j]]++] = j;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            int j = sa[i] - 1;
            if (j >= 0 && (type[j] == TYPE_S || type[j] >= 0)) {
                sa[--S[a[j]]] = j;
            }
        }
        return sa;
    };
    int SS = lmsID.size();
    vector<int> ordLms;
    for (int i : inducedSort(a, lmsID, type)) {
        if (type[i] >= 0) {
            ordLms.push_back(i);
        }
    }
    reverse(lmsID.begin(), lmsID.end());
    vector<int> rankLms(SS);
    for (int i = 1; i < SS; i++) {
        int x = type[ordLms[i - 1]];
        int y = type[ordLms[i]];
        rankLms[i] = rankLms[i - 1] + (lms[x] < lms[y]);
    }
    for (int i = 0; i < SS; i++) {
        type[ordLms[i]] = rankLms[i];
    }
    vector<int> lmsA;
    for (int i : lmsID) {
        lmsA.push_back(type[i]);
    }
    vector<int> ordSS;
    for (int i : sufarray(lmsA)) {
        ordSS.push_back(lmsID[i]);
    }
    return inducedSort(a, ordSS, type);
}
vector<int> lcparray(const vector<int> &s, const vector<int> &sa) {
    const int n = s.size() - 1;
    vector<int> isa(n + 1), lcp(n + 1);
    for (int i = 0; i <= n; i++) {
        isa[sa[i]] = i;
    }
    int k = 0;
    for (int i = 0; i < n; i++) {
        int j = sa[isa[i] - 1];
        k = max(0, k - 1);
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[isa[i] - 1] = k;
    }
    return lcp;
}
struct RMQ {
    vector<int> lg;
    vector<vector<int>> dat;
    RMQ(const vector<int> &a) {
        const int n = a.size();
        lg.resize(n + 1);
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i / 2] + 1;
        }
        const int m = lg[n];
        dat.assign(m + 1, vector<int>(n));
        for (int i = 0; i < n; i++) {
            dat[0][i] = a[i];
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j + (1 << i) < n; j++) {
                dat[i + 1][j] = min(dat[i][j], dat[i][j + (1 << i)]);
            }
        }
    }
    int getmin(int l, int r) {
        int k = lg[r - l];
        return min(dat[k][l], dat[k][r - (1 << k)]);
    }
};
int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    vector<int> start(n);
    vector<int> t;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        start[i] = t.size();
        for (char c : s[i]) {
            t.push_back(c);
        }
        t.push_back(i + 'z' + 1);
    }
    t.push_back(0);
    auto sa = sufarray(t);
    auto lcp = lcparray(t, sa);
    vector<int> isa(t.size());
    for (int i = 0; i < t.size(); i++) {
        isa[sa[i]] = i;
    }
    RMQ rmq(lcp);
    int m, x, d;
    cin >> m >> x >> d;
    long long ans = 0;
    for (int k = 0; k < m; k++) {
        int i = (x / (n - 1)) + 1;
        int j = (x % (n - 1)) + 1;
        if (i > j) {
            swap(i, j);
        } else {
            j = j + 1;
        }
        x = (x + d) % (1LL * n * (n - 1));
        i--;
        j--;
        if (isa[start[i]] > isa[start[j]]) {
            swap(i, j);
        }
        if (i == j) {
            ans += s[i].size();
        } else {
            ans += rmq.getmin(isa[start[i]], isa[start[j]]);
        }
    }
    cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0