結果

問題 No.1018 suffixsuffixsuffix
ユーザー pekempey
提出日時 2020-04-03 22:31:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,587 bytes
コンパイル時間 1,847 ms
コンパイル使用メモリ 176,660 KB
実行使用メモリ 6,812 KB
最終ジャッジ日時 2024-07-03 04:36:16
合計ジャッジ時間 7,792 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22 WA * 12
権限があれば一括ダウンロードができます

ソースコード

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