結果

問題 No.515 典型LCP
コンテスト
ユーザー くれちー
提出日時 2017-07-27 23:50:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 266 ms / 1,000 ms
コード長 1,730 bytes
コンパイル時間 788 ms
コンパイル使用メモリ 76,624 KB
実行使用メモリ 14,856 KB
最終ジャッジ日時 2024-10-10 02:18:07
合計ジャッジ時間 4,051 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#define REP(i, n) FOR(i, 0, n - 1, 1)
#define FOR(i, a, b, c) for (ll i = a; i <= (ll)b; i += c)
typedef long long ll;

#define MAX_N 100000

int lcp(std::string a, std::string b) {
    int len = std::min(a.length(), b.length());
    int i = 0;
    for (; i < len; i++) if (a[i] != b[i]) break;
    return i;
}

int main() {
    int n;
    std::cin >> n;
    static std::string s[MAX_N];
    REP(i, n) std::cin >> s[i];
    int m; ll x, d;
    std::cin >> m >> x >> d;

    static int bsi[MAX_N];
    REP(i, n) bsi[i] = i;
    std::sort(bsi, bsi + n, [](int& x, int& y) { return s[x] > s[y]; });

    static int asi[MAX_N];
    REP(i, n) asi[bsi[i]] = i;

    static int lcplen[MAX_N];
    REP(i, n - 1) lcplen[i] = lcp(s[bsi[i]], s[bsi[i + 1]]);

    static int logTable[MAX_N] = {};
    FOR(i, 2, n - 1, 1) logTable[i] = logTable[i >> 1] + 1;

    static int table[MAX_N - 1][17];
    REP(i, n - 1) table[i][0] = i;
    for (int k = 1; (1 << k) < n - 1; k++) {
        for (int i = 0; i + (1 << k) <= n - 1; i++) {
            int a = table[i][k - 1];
            int b = table[i + (1 << (k - 1))][k - 1];
            table[i][k] = lcplen[a] < lcplen[b] ? a : b;
        }
    }

    ll ans = 0;
    ll mod = (ll)n * (n - 1);

    REP(_, m) {
        int i = x / (n - 1);
        int j = x % (n - 1);
        if (i > j) std::swap(i, j); else j++;

        int p = asi[i];
        int q = asi[j];
        if (p > q) std::swap(p, q);
        int k = logTable[q - 1 - p];
        ans += std::min(lcplen[table[p][k]], lcplen[table[q - (1 << k)][k]]);

        x = (x + d) % mod;
    }

    std::cout << ans << std::endl;
    return 0;
}
0