結果

問題 No.515 典型LCP
ユーザー
提出日時 2017-05-10 12:40:00
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 253 ms / 1,000 ms
コード長 2,682 bytes
コンパイル時間 1,341 ms
コンパイル使用メモリ 96,292 KB
実行使用メモリ 14,344 KB
最終ジャッジ日時 2023-10-13 10:00:41
合計ジャッジ時間 4,666 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 253 ms
14,344 KB
testcase_01 AC 247 ms
14,288 KB
testcase_02 AC 139 ms
11,108 KB
testcase_03 AC 3 ms
8,292 KB
testcase_04 AC 3 ms
8,300 KB
testcase_05 AC 105 ms
11,172 KB
testcase_06 AC 110 ms
11,364 KB
testcase_07 AC 105 ms
11,064 KB
testcase_08 AC 125 ms
11,292 KB
testcase_09 AC 115 ms
11,956 KB
testcase_10 AC 115 ms
11,816 KB
testcase_11 AC 115 ms
11,776 KB
testcase_12 AC 113 ms
11,908 KB
testcase_13 AC 106 ms
11,156 KB
testcase_14 AC 21 ms
11,032 KB
testcase_15 AC 96 ms
8,872 KB
testcase_16 AC 96 ms
8,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

//#define DEBUG
#ifdef DEBUG
#define debug_printf printf
#else
#define debug_printf 1 ? 0 : printf
#endif

using namespace std;
typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;

#define FST first
#define SND second

#define MAX_N   (100000)                  // 10^5
#define MAX_LOGN   (17)
#define MAX_M   (3000000)                  // 10^5
// #define MAX_N   (1000000000)              // 10^9
// #define MAX_N   (1000000000000000000)     // 10^18
#define BASE    (1000000000 + 7)          // 10^9 + 7
#define INFI    (1000000000 + 7)          // 10^9 + 7
#define INFL    (1000000000000000000 + 7) // 10^18 + 7

ll N, M, X, D;
pair<string, int> S[MAX_N];
int MP[MAX_N];
int ST[MAX_LOGN][MAX_N];

int common_prefix_size(const string &s, const string &t) {
  int n = min(s.size(), t.size());
  for (int i = 0; i < n; i++) if (s[i] != t[i]) return i;
  return n;
}

void contruct_sparse_table() {
  for (int i = 0; i < N - 1; i++) ST[0][i] = common_prefix_size(S[i].FST, S[i + 1].FST);

  for (int k = 1; (1 << k) < N; k++) {
    int p = 1 << (k - 1);
    for (int i = 0; i < N - 1; i++) {
      ST[k][i] = ST[k - 1][i];
      if (i + p < N - 1) ST[k][i] = min(ST[k][i], ST[k - 1][i + p]);
    }
  }

#ifdef DEBUG
  for (int k = 0; (1 << k) < N; k++) {
    for (int i = 0; i < N - 1; i++)
      debug_printf("%d ", ST[k][i]);
    debug_printf("\n");
  }
#endif
}

ll query(int l, int r) {
  int d = r - l;
  if (d == 0) return S[l].FST.size();
  int k = 0;
  while ((1 << k) <= d) k++;
  k--;
  int p = 1 << k;
  return min(ST[k][l], ST[k][r - p]);
}

void solve() {
  sort(S, S + N);
  for (int i = 0; i < N; i++) MP[S[i].SND] = i;

  contruct_sparse_table();
  ll ans = 0;
  for (int i = 0; i < M; i++) {
    ll l = (X / (N - 1)) + 1;
    ll r = (X % (N - 1)) + 1;
    if (l > r)
      swap(l, r);
    else
      r++;
    X = (X + D) % (N * (N - 1));
    l--; r--;

    l = MP[l]; r = MP[r];
    if (l > r) swap(l, r);
    debug_printf("S[%lld] = %s, S[%lld] = %s\n", l, S[l].FST.c_str(), r, S[r].FST.c_str());
    ans += query(l, r);
  }
  cout << ans << endl;
}

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> S[i].FST;
    S[i].SND = i;
  }
  cin >> M >> X >> D;

  solve();

  return 0;
}
0