結果
| 問題 | No.515 典型LCP |
| ユーザー |
 arktan763
|
| 提出日時 | 2019-11-16 20:36:31 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,873 bytes |
| コンパイル時間 | 2,064 ms |
| コンパイル使用メモリ | 182,772 KB |
| 実行使用メモリ | 214,216 KB |
| 最終ジャッジ日時 | 2023-10-25 10:18:37 |
| 合計ジャッジ時間 | 6,913 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x) \
for(auto &youso_ : (x)) cin >> youso_
#define bitcnt(x) __builtin_popcount(x)
#define lbit(x) __builtin_ffsll(x)
#define rbit(x) __builtin_clzll(x)
#define SZ(x) ((ll)(x).size())
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
#define rAll(a) (a).rbegin(), (a).rend()
template <typename T = long long> inline T IN() {
T x;
cin >> x;
return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
cin >> head;
CIN(move(tail)...);
}
#define CCIN(...) \
char __VA_ARGS__; \
CIN(__VA_ARGS__)
#define DCIN(...) \
double __VA_ARGS__; \
CIN(__VA_ARGS__)
#define LCIN(...) \
ll __VA_ARGS__; \
CIN(__VA_ARGS__)
#define SCIN(...) \
string __VA_ARGS__; \
CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v) \
{ \
FOREACH(x, v) { cout << x << " "; } \
cout << "\n"; \
}
template <typename T = string> inline void eputs(T s) {
cout << s << "\n";
exit(0);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
std::fill((T *)array, (T *)(array + N), val);
}
template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using PQ = priority_queue<T>;
typedef long long ll;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<ll, ll> PL;
typedef vector<PL> VPL;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;
// const double PI = atan(1.0) * 4.0;
const ll dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
#define PI 3.141592653589793238
// Sparse Table
template <class MeetSemiLattice> struct SparseTable {
vector<vector<MeetSemiLattice>> dat;
vector<int> height;
SparseTable() {}
SparseTable(const vector<MeetSemiLattice> &vec) { init(vec); }
void init(const vector<MeetSemiLattice> &vec) {
int n = (int)vec.size(), h = 0;
while((1 << h) < n) ++h;
dat.assign(h, vector<MeetSemiLattice>(1 << h));
height.assign(n + 1, 0);
for(int i = 2; i <= n; i++) height[i] = height[i >> 1] + 1;
for(int i = 0; i < n; ++i) dat[0][i] = vec[i];
for(int i = 1; i < h; ++i)
for(int j = 0; j < n; ++j)
dat[i][j] = min(dat[i - 1][j], dat[i - 1][min(j + (1 << (i - 1)), n - 1)]);
}
MeetSemiLattice get(int a, int b) {
return min(dat[height[b - a]][a], dat[height[b - a]][b - (1 << height[b - a])]);
}
};
// Suffix Array ( Manber&Myers: O(n (logn)^2) )
struct SuffixArray {
string str;
vector<int> sa; // sa[i] : the starting index of the i-th smallest suffix (i = 0, 1, ..., n)
vector<int> lcp; // lcp[i]: the lcp of sa[i] and sa[i+1] (i = 0, 1, ..., n-1)
inline int &operator[](int i) { return sa[i]; }
SuffixArray(const string &str_) : str(str_) {
buildSA();
calcLCP();
}
void init(const string &str_) {
str = str_;
buildSA();
calcLCP();
}
// build SA
vector<int> rank_sa, tmp_rank_sa;
struct CompareSA {
int n, k;
const vector<int> &rank;
CompareSA(int n, int k, const vector<int> &rank_sa)
: n(n), k(k), rank(rank_sa) {}
bool operator()(int i, int j) {
if(rank[i] != rank[j])
return (rank[i] < rank[j]);
else {
int rank_ik = (i + k <= n ? rank[i + k] : -1);
int rank_jk = (j + k <= n ? rank[j + k] : -1);
return (rank_ik < rank_jk);
}
}
};
void buildSA() {
int n = (int)str.size();
sa.resize(n + 1), lcp.resize(n + 1), rank_sa.resize(n + 1), tmp_rank_sa.resize(n + 1);
for(int i = 0; i < n; ++i) sa[i] = i, rank_sa[i] = (int)str[i];
sa[n] = n, rank_sa[n] = -1;
for(int k = 1; k <= n; k *= 2) {
CompareSA csa(n, k, rank_sa);
sort(sa.begin(), sa.end(), csa);
tmp_rank_sa[sa[0]] = 0;
for(int i = 1; i <= n; ++i) {
tmp_rank_sa[sa[i]] = tmp_rank_sa[sa[i - 1]];
if(csa(sa[i - 1], sa[i])) ++tmp_rank_sa[sa[i]];
}
for(int i = 0; i <= n; ++i) rank_sa[i] = tmp_rank_sa[i];
}
}
vector<int> rsa;
SparseTable<int> st;
void calcLCP() {
int n = (int)str.size();
rsa.resize(n + 1);
for(int i = 0; i <= n; ++i) rsa[sa[i]] = i;
lcp.resize(n + 1);
lcp[0] = 0;
int cur = 0;
for(int i = 0; i < n; ++i) {
int pi = sa[rsa[i] - 1];
if(cur > 0) --cur;
for(; pi + cur < n && i + cur < n; ++cur) {
if(str[pi + cur] != str[i + cur]) break;
}
lcp[rsa[i] - 1] = cur;
}
st.init(lcp);
}
// calc lcp
int getLCP(int a, int b) { // lcp of str.sutstr(a) and str.substr(b)
return st.get(min(rsa[a], rsa[b]), max(rsa[a], rsa[b]));
}
};
signed main() {
LCIN(N);
cin.tie(0);
ios::sync_with_stdio(false);
string s = "";
VL len(N), sum(N + 1);
REP(i, N) {
SCIN(S);
len[i] = S.length();
s += S + (i == N - 1 ? "" : "$");
}
REP(i, N) { sum[i + 1] += sum[i] + len[i] + 1; }
SuffixArray SA(s);
LCIN(M, x, d);
ll ans = 0;
REP(loop, M) {
ll i = (x / (N - 1)) + 1, j = (x % (N - 1)) + 1;
if(i > j)
swap(i, j);
else
j++;
x = (x + d) % (N * (N - 1));
i--, j--;
}
cout << ans << "\n";
}