結果

問題 No.515 典型LCP
コンテスト
ユーザー arktan763
提出日時 2019-11-16 20:36:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,873 bytes
コンパイル時間 2,245 ms
コンパイル使用メモリ 183,280 KB
実行使用メモリ 214,124 KB
最終ジャッジ日時 2024-09-25 05:20:19
合計ジャッジ時間 23,461 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 1 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define bitcnt(x) __builtin_popcount(x)
#define lbit(x) __builtin_ffsll(x)
#define rbit(x) __builtin_clzll(x)
#define SZ(x) ((ll)(x).size())
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
#define rAll(a) (a).rbegin(), (a).rend()

template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CCIN(...)                                                              \
    char __VA_ARGS__;                                                          \
    CIN(__VA_ARGS__)
#define DCIN(...)                                                              \
    double __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v)                                                              \
    {                                                                          \
        FOREACH(x, v) { cout << x << " "; }                                    \
        cout << "\n";                                                          \
    }
template <typename T = string> inline void eputs(T s) {
    cout << s << "\n";
    exit(0);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *)array, (T *)(array + N), val);
}

template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using PQ = priority_queue<T>;

typedef long long ll;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<ll, ll> PL;
typedef vector<PL> VPL;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;
// const double PI = atan(1.0) * 4.0;
const ll dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
#define PI 3.141592653589793238

// Sparse Table
template <class MeetSemiLattice> struct SparseTable {
    vector<vector<MeetSemiLattice>> dat;
    vector<int> height;

    SparseTable() {}
    SparseTable(const vector<MeetSemiLattice> &vec) { init(vec); }
    void init(const vector<MeetSemiLattice> &vec) {
        int n = (int)vec.size(), h = 0;
        while((1 << h) < n) ++h;
        dat.assign(h, vector<MeetSemiLattice>(1 << h));
        height.assign(n + 1, 0);
        for(int i = 2; i <= n; i++) height[i] = height[i >> 1] + 1;
        for(int i = 0; i < n; ++i) dat[0][i] = vec[i];
        for(int i = 1; i < h; ++i)
            for(int j = 0; j < n; ++j)
                dat[i][j] = min(dat[i - 1][j], dat[i - 1][min(j + (1 << (i - 1)), n - 1)]);
    }

    MeetSemiLattice get(int a, int b) {
        return min(dat[height[b - a]][a], dat[height[b - a]][b - (1 << height[b - a])]);
    }
};

// Suffix Array ( Manber&Myers: O(n (logn)^2) )
struct SuffixArray {
    string str;
    vector<int> sa; // sa[i] : the starting index of the i-th smallest suffix (i = 0, 1, ..., n)
    vector<int> lcp; // lcp[i]: the lcp of sa[i] and sa[i+1] (i = 0, 1, ..., n-1)
    inline int &operator[](int i) { return sa[i]; }

    SuffixArray(const string &str_) : str(str_) {
        buildSA();
        calcLCP();
    }
    void init(const string &str_) {
        str = str_;
        buildSA();
        calcLCP();
    }

    // build SA
    vector<int> rank_sa, tmp_rank_sa;
    struct CompareSA {
        int n, k;
        const vector<int> &rank;
        CompareSA(int n, int k, const vector<int> &rank_sa)
            : n(n), k(k), rank(rank_sa) {}
        bool operator()(int i, int j) {
            if(rank[i] != rank[j])
                return (rank[i] < rank[j]);
            else {
                int rank_ik = (i + k <= n ? rank[i + k] : -1);
                int rank_jk = (j + k <= n ? rank[j + k] : -1);
                return (rank_ik < rank_jk);
            }
        }
    };
    void buildSA() {
        int n = (int)str.size();
        sa.resize(n + 1), lcp.resize(n + 1), rank_sa.resize(n + 1), tmp_rank_sa.resize(n + 1);
        for(int i = 0; i < n; ++i) sa[i] = i, rank_sa[i] = (int)str[i];
        sa[n] = n, rank_sa[n] = -1;
        for(int k = 1; k <= n; k *= 2) {
            CompareSA csa(n, k, rank_sa);
            sort(sa.begin(), sa.end(), csa);
            tmp_rank_sa[sa[0]] = 0;
            for(int i = 1; i <= n; ++i) {
                tmp_rank_sa[sa[i]] = tmp_rank_sa[sa[i - 1]];
                if(csa(sa[i - 1], sa[i])) ++tmp_rank_sa[sa[i]];
            }
            for(int i = 0; i <= n; ++i) rank_sa[i] = tmp_rank_sa[i];
        }
    }
    vector<int> rsa;
    SparseTable<int> st;
    void calcLCP() {
        int n = (int)str.size();
        rsa.resize(n + 1);
        for(int i = 0; i <= n; ++i) rsa[sa[i]] = i;
        lcp.resize(n + 1);
        lcp[0] = 0;
        int cur = 0;
        for(int i = 0; i < n; ++i) {
            int pi = sa[rsa[i] - 1];
            if(cur > 0) --cur;
            for(; pi + cur < n && i + cur < n; ++cur) {
                if(str[pi + cur] != str[i + cur]) break;
            }
            lcp[rsa[i] - 1] = cur;
        }
        st.init(lcp);
    }

    // calc lcp
    int getLCP(int a, int b) { // lcp of str.sutstr(a) and str.substr(b)
        return st.get(min(rsa[a], rsa[b]), max(rsa[a], rsa[b]));
    }
};

signed main() {
    LCIN(N);
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s = "";
    VL len(N), sum(N + 1);
    REP(i, N) {
        SCIN(S);
        len[i] = S.length();
        s += S + (i == N - 1 ? "" : "$");
    }
    REP(i, N) { sum[i + 1] += sum[i] + len[i] + 1; }
    SuffixArray SA(s);
    LCIN(M, x, d);
    ll ans = 0;
    REP(loop, M) {
        ll i = (x / (N - 1)) + 1, j = (x % (N - 1)) + 1;
        if(i > j)
            swap(i, j);
        else
            j++;
        x = (x + d) % (N * (N - 1));
        i--, j--;
    }
    cout << ans << "\n";
}
0