結果
問題 | No.2858 Make a Palindrome |
ユーザー |
![]() |
提出日時 | 2024-08-25 16:23:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 409 ms / 3,000 ms |
コード長 | 1,685 bytes |
コンパイル時間 | 794 ms |
コンパイル使用メモリ | 74,808 KB |
実行使用メモリ | 15,256 KB |
最終ジャッジ日時 | 2024-08-25 16:23:18 |
合計ジャッジ時間 | 4,222 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
//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, mana2[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;}