結果
問題 | No.2858 Make a Palindrome |
ユーザー |
![]() |
提出日時 | 2024-08-25 16:22:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,684 bytes |
コンパイル時間 | 964 ms |
コンパイル使用メモリ | 74,736 KB |
実行使用メモリ | 15,256 KB |
最終ジャッジ日時 | 2024-08-25 16:22:36 |
合計ジャッジ時間 | 7,410 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 20 RE * 19 |
ソースコード
//abaabaxyz (X=rev(X), Y≠rev(X), X=abc, Y=xyz) #include <iostream> #include <algorithm> #include <vector> #include <string> #define int long long #define rep(i, n) for(i = 0; i < n; i++) using namespace std; vector<int> manacher(string S) { vector<int> R(S.size()); int i = 0, j = 0; while (i < S.size()) { while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j; R[i] = j; int k = 1; while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k; i += k; j -= k; } return R; } string makeDumy(string s) { int i, n = s.length(); string t = "-"; rep(i, n) { t += s[i]; t += '-'; } return t; } int solve(int n, int m, string s) { int i; string t = makeDumy(s); vector<int> mana = manacher(t); //単独のsで条件を満たせるかを判定しておく int longest = 0; rep(i, mana.size()) { longest = max(longest, mana[i] - 1); } if (longest >= m) return 1; //2回連結するケース XXY (Y≠rev(X), X=rev(X)など) string t2 = makeDumy(s + s); vector<int> mana2 = manacher(t2); longest = 0; rep(i, mana2.size()) { longest = max(longest, mana[i] - 1); } if (longest >= m) return 2; //先頭i文字, 末尾n-i文字が回文かどうか const int INF = 1e+15; int ret = INF; rep(i, n) { //t[2 * i]にある$で分ける int c = 2 * i; if (mana[c - i] - 1 < i) continue; if (mana[c + n - i] - 1 < n - i) continue; int x = i; int y = n - i; int cnt = ((m + min(x, y)) + (x + y - 1)) / (x + y); ret = min(ret, cnt); } if (ret >= INF) return -1; return ret; } signed main() { int T; cin >> T; while (T--) { int n, m; string s; cin >> n >> m >> s; int res = solve(n, m, s); cout << res << endl; } return 0; }