結果

問題 No.515 典型LCP
ユーザー くれちーくれちー
提出日時 2017-07-27 23:50:13
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 276 ms / 1,000 ms
コード長 1,730 bytes
コンパイル時間 1,023 ms
コンパイル使用メモリ 76,840 KB
実行使用メモリ 14,976 KB
最終ジャッジ日時 2024-04-18 09:00:41
合計ジャッジ時間 4,082 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 276 ms
14,976 KB
testcase_01 AC 265 ms
14,976 KB
testcase_02 AC 140 ms
7,552 KB
testcase_03 AC 3 ms
6,784 KB
testcase_04 AC 5 ms
6,784 KB
testcase_05 AC 101 ms
7,680 KB
testcase_06 AC 102 ms
7,552 KB
testcase_07 AC 100 ms
7,508 KB
testcase_08 AC 130 ms
7,680 KB
testcase_09 AC 105 ms
8,320 KB
testcase_10 AC 107 ms
8,216 KB
testcase_11 AC 108 ms
8,308 KB
testcase_12 AC 110 ms
8,320 KB
testcase_13 AC 103 ms
7,620 KB
testcase_14 AC 21 ms
7,424 KB
testcase_15 AC 100 ms
7,296 KB
testcase_16 AC 98 ms
7,296 KB
権限があれば一括ダウンロードができます

ソースコード

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