結果
問題 |
No.515 典型LCP
|
ユーザー |
![]() |
提出日時 | 2025-03-14 00:12:25 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 833 ms / 1,000 ms |
コード長 | 1,925 bytes |
コンパイル時間 | 1,971 ms |
コンパイル使用メモリ | 161,704 KB |
実行使用メモリ | 17,064 KB |
最終ジャッジ日時 | 2025-03-14 00:12:35 |
合計ジャッジ時間 | 8,041 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h> #define rep(i, l, r) for (int i = (l); i <= (r); i++) #define per(i, r, l) for (int i = (r); i >= (l); i--) #define int long long #define debug(x) cout << #x << '=' << x << '\n' #define all(vc) ((vc).begin(), (vc).end()) #define SZ(vc) (int)((vc).size()) #define pb push_back using namespace std; template<typename tp> inline void tomax(tp &a, tp b) { a=(b>a?b:a); } template<typename tp> inline void tomin(tp &a, tp b) { a=(b<a?b:a); } template<typename tp> inline void read(tp& n) { tp x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); n = x * f; } template<typename tp> inline void write(tp x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } typedef unsigned long long ULL; typedef long long LL; typedef pair<int, int> PII; typedef __int128 int128; typedef double db; const int N = 1e5 + 5; int n; string s[N]; int m,x,d; vector<int> h[N]; bool check(int a, int b, int c) { if (min(SZ(s[a]),SZ(s[b]))<c)return 0; return h[a][c] == h[b][c]; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); cin >> n; rep(i, 1, n) { cin >> s[i]; h[i].resize(SZ(s[i])+1, 0); int pw=1; rep(j, 1, SZ(s[i])) h[i][j] = h[i][j-1]+pw*s[i][j-1],pw*=131; } cin >> m >> x >>d; int ans = 0; rep(i, 1, m) { int a = (x/(n-1))+1, b = (x%(n-1))+1; if (a>b) swap(a,b); else b+=1; x = (x+d) % (n*(n-1)); int l = 0, r = 1e6; r += 1; while (l<r) { int mid = (l+r>>1); if (check(a,b,mid)) l = mid+1; else r = mid; } ans+=l-1; } cout << ans << '\n'; return 0; }