結果
問題 | No.515 典型LCP |
ユーザー |
![]() |
提出日時 | 2017-05-05 22:48:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 618 ms / 1,000 ms |
コード長 | 1,172 bytes |
コンパイル時間 | 839 ms |
コンパイル使用メモリ | 79,740 KB |
実行使用メモリ | 19,260 KB |
最終ジャッジ日時 | 2024-09-14 09:54:12 |
合計ジャッジ時間 | 5,834 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#include<iostream> #include<algorithm> #include<string> #include<vector> #include<map> using namespace std; #pragma warning(disable:4996) long long N, M, x, d, sum; string S[100009]; vector<long long>E[100009]; char c[10000009]; bool compare(long long a1, long long a2, long long a3) { if (S[a1].size() < a3 || S[a2].size() < a3)return false; if (E[a1][a3] == E[a2][a3])return true; return false; } int main() { cin >> N; for (int i = 1; i <= N; i++) { scanf("%s", c); int pos = 0; while (c[pos]) { S[i] += c[pos]; pos++; } E[i].resize(S[i].size() + 2, 0); long long Y = 1; for (int j = 1; j <= S[i].size(); j++) { E[i][j] = E[i][j - 1] + (Y*(long long)(S[i][j - 1])); Y *= 257; } } cin >> M >> x >> d; for (int i = 1; i <= M; i++) { long long A = (x / (N - 1)) + 1; long long B = (x % (N - 1)) + 1; if (A > B)swap(A, B); else B = B + 1; x = (x + d) % (N * (N - 1)); long long L = 0, R = 1000000, M; while (true) { M = (L + R) / 2; bool p1 = compare(A, B, M), p2 = compare(A, B, M + 1); if (p1 == true && p2 == false)break; else if (p1 == false)R = M; else L = M; } sum += M; } cout << sum << endl; return 0; }