結果

問題 No.1018 suffixsuffixsuffix
ユーザー pekempeypekempey
提出日時 2020-04-03 22:31:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,587 bytes
コンパイル時間 1,792 ms
コンパイル使用メモリ 175,528 KB
実行使用メモリ 6,692 KB
最終ジャッジ日時 2023-09-16 03:17:40
合計ジャッジ時間 7,942 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 167 ms
6,472 KB
testcase_15 AC 166 ms
6,424 KB
testcase_16 AC 186 ms
6,500 KB
testcase_17 AC 161 ms
6,452 KB
testcase_18 AC 161 ms
6,460 KB
testcase_19 AC 19 ms
4,380 KB
testcase_20 AC 19 ms
4,376 KB
testcase_21 AC 20 ms
4,380 KB
testcase_22 AC 19 ms
4,380 KB
testcase_23 AC 20 ms
4,376 KB
testcase_24 AC 174 ms
6,380 KB
testcase_25 AC 191 ms
6,536 KB
testcase_26 AC 167 ms
6,448 KB
testcase_27 AC 165 ms
6,412 KB
testcase_28 AC 164 ms
6,420 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 AC 20 ms
4,376 KB
testcase_36 WA -
testcase_37 AC 182 ms
6,448 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

vector<int> SA(string s) {
  s += '$';
  const int n = s.size();
  vector<int> sa(n);
  vector<int> ra(n);
  for (int i = 0; i <= n; i++) {
    sa[i] = i;
    ra[i] = s[i];
  }
  for (int k = 1; k < n; k *= 2) {
    auto cmp = [&](int i, int j) {
      if (ra[i] != ra[j]) return ra[i] < ra[j];
      return (i + k < n ? ra[i + k] : 0) < (j + k < n ? ra[j + k] : 0);
    };
    sort(sa.begin(), sa.end(), cmp);
    vector<int> tmp(ra);
    tmp[sa[0]] = 0;
    for (int i = 0; i + 1 < n; i++) {
      tmp[sa[i + 1]] = tmp[sa[i]] + cmp(sa[i], sa[i + 1]);
    }
    ra = move(tmp);
  }
  return sa;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  ll N, M, Q; cin >> N >> M >> Q;
  string S; cin >> S;
  vector<ll> K(Q); rep(i, Q) cin >> K[i];
  if (M == 1) {
    auto sa = SA(S);
    rep(i, Q) cout << sa[K[i]] << ' ';
    return 0;
  }
  auto sa = SA(S + S);
  ll now = 0;
  ll cnt = 0;
  rep(i, Q) {
    while (true) {
      if (sa[now] >= N) {
        if (K[i] == cnt) {
          cout << N*M-N+sa[now]-N+1 << ' ';
          break;
        } else {
          cnt++;
          now++;
        }
      } else {
        if (K[i] <= cnt + M-2) {
          ll d = K[i] - cnt;
          cout << N*M-2*N-d*N+sa[now]+1 << ' ';
          break;
        } else {
          cnt += M - 1;
          now++;
        }
      }
    }
  }
}
0