結果
問題 | No.2858 Make a Palindrome |
ユーザー | SnowBeenDiding |
提出日時 | 2024-08-28 19:29:36 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 468 ms / 3,000 ms |
コード長 | 5,998 bytes |
コンパイル時間 | 5,519 ms |
コンパイル使用メモリ | 316,720 KB |
実行使用メモリ | 43,224 KB |
最終ジャッジ日時 | 2024-08-28 19:30:21 |
合計ジャッジ時間 | 10,711 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 468 ms
6,812 KB |
testcase_01 | AC | 121 ms
6,944 KB |
testcase_02 | AC | 117 ms
6,940 KB |
testcase_03 | AC | 121 ms
6,944 KB |
testcase_04 | AC | 118 ms
6,948 KB |
testcase_05 | AC | 96 ms
6,940 KB |
testcase_06 | AC | 71 ms
6,940 KB |
testcase_07 | AC | 70 ms
6,940 KB |
testcase_08 | AC | 70 ms
6,940 KB |
testcase_09 | AC | 72 ms
6,944 KB |
testcase_10 | AC | 83 ms
6,944 KB |
testcase_11 | AC | 84 ms
6,940 KB |
testcase_12 | AC | 83 ms
6,944 KB |
testcase_13 | AC | 84 ms
6,940 KB |
testcase_14 | AC | 83 ms
6,944 KB |
testcase_15 | AC | 50 ms
6,944 KB |
testcase_16 | AC | 55 ms
6,940 KB |
testcase_17 | AC | 52 ms
6,940 KB |
testcase_18 | AC | 56 ms
6,940 KB |
testcase_19 | AC | 56 ms
6,940 KB |
testcase_20 | AC | 52 ms
38,112 KB |
testcase_21 | AC | 54 ms
38,876 KB |
testcase_22 | AC | 32 ms
21,808 KB |
testcase_23 | AC | 50 ms
38,028 KB |
testcase_24 | AC | 45 ms
34,012 KB |
testcase_25 | AC | 42 ms
30,060 KB |
testcase_26 | AC | 40 ms
28,840 KB |
testcase_27 | AC | 58 ms
42,628 KB |
testcase_28 | AC | 46 ms
31,888 KB |
testcase_29 | AC | 54 ms
39,564 KB |
testcase_30 | AC | 59 ms
43,040 KB |
testcase_31 | AC | 59 ms
43,148 KB |
testcase_32 | AC | 56 ms
43,012 KB |
testcase_33 | AC | 59 ms
43,144 KB |
testcase_34 | AC | 58 ms
43,052 KB |
testcase_35 | AC | 58 ms
43,044 KB |
testcase_36 | AC | 59 ms
43,140 KB |
testcase_37 | AC | 57 ms
43,164 KB |
testcase_38 | AC | 59 ms
43,224 KB |
testcase_39 | AC | 58 ms
43,204 KB |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace atcoder; using namespace std; typedef long long ll; template <typename T> T ceil_div(T a, T b) { if (b < 0) a = -a, b = -b; return (a >= 0 ? (a + b - 1) / b : a / b); } struct RollingHash { int n; static const ll base1 = 1009; static const ll base2 = 2009; static const ll mod1 = 1000000007; static const ll mod2 = 1000000009; vector<ll> hash1, hash2, pow1, pow2; RollingHash() {} RollingHash(const string &S) { n = (int)S.size(); hash1.assign(n + 1, 0); hash2.assign(n + 1, 0); pow1.assign(n + 1, 1); pow2.assign(n + 1, 1); for (int i = 0; i < n; ++i) { hash1[i + 1] = (hash1[i] * base1 + S[i]) % mod1; hash2[i + 1] = (hash2[i] * base2 + S[i]) % mod2; pow1[i + 1] = (pow1[i] * base1) % mod1; pow2[i + 1] = (pow2[i] * base2) % mod2; } } /** * S の [l, r) のハッシュ値を返す * O(1) */ inline pair<ll, ll> get(int l, int r) const { ll res1 = hash1[r] - hash1[l] * pow1[r - l] % mod1; if (res1 < 0) res1 += mod1; ll res2 = hash2[r] - hash2[l] * pow2[r - l] % mod2; if (res2 < 0) res2 += mod2; return make_pair(res1, res2); } /** * S のハッシュ値を返す * O(1) */ inline pair<ll, ll> hash() const { return get(0, (int)hash1.size() - 1); } /** * LCP (Longest Common Prefix) * O( log N ) */ inline int getLCP(int a, int b) const { int len = min((int)hash1.size() - a, (int)hash1.size() - b); int low = 0, high = len; while (high - low > 1) { int mid = (low + high) >> 1; if (get(a, a + mid) != get(b, b + mid)) high = mid; else low = mid; } return low; } /** * hash h1 と 長さ h2_len の文字列の hash h2 を結合 */ pair<ll, ll> concat(pair<ll, ll> h1, pair<ll, ll> h2, ll h2_len) { if (h2_len < pow1.size()) return make_pair((h1.first * pow1[h2_len] + h2.first) % mod1, (h1.second * pow2[h2_len] + h2.second) % mod2); return make_pair( (h1.first * pow_mod(base1, h2_len + 1, mod1) + h2.first) % mod1, (h1.second * pow_mod(base2, h2_len + 1, mod2) + h2.second) % mod2); } /** * 文字列の最小周期を返す */ int max_repeat(bool multiple_only = false) { for (int i = 1; i < n; i++) { if (multiple_only && n % i != 0) continue; if (n - i < i) break; if (get(0, n - i) == get(i, n)) { return i; } } return n; } /** * hash h を count 回結合 (WIP) */ pair<ll, ll> times(pair<ll, ll> h, ll len, ll count) { pair<ll, ll> ret = {0, 0}, now = h; ll pw = 1; while (count) { if (count & 1) ret = concat(ret, now, len * pw); now = concat(now, now, len * pw); count >>= 1; pw <<= 1; } return ret; } }; int max_pal_len(string s) { // 回文の最大半径を返す int ret = 0; // 奇数長 vector<int> odd(s.size()); for (int i = 0, l = 0, r = -1; i < s.size(); i++) { int k = (i > r) ? 1 : min(odd[l + r - i], r - i); while (0 <= i - k && i + k < s.size() && s[i - k] == s[i + k]) k++; odd[i] = k--; ret = max(ret, k * 2 + 1); if (i + k > r) l = i - k, r = i + k; } ret = max(ret, *max_element(odd.begin(), odd.end()) * 2 - 1); // 偶数長 vector<int> even(s.size()); for (int i = 0, l = 0, r = -1; i < s.size(); i++) { int k = (i > r) ? 0 : min(even[l + r - i + 1], r - i + 1); while (0 <= i - k - 1 && i + k < s.size() && s[i - k - 1] == s[i + k]) k++; even[i] = k--; ret = max(ret, k * 2); if (i + k > r) l = i - k - 1, r = i + k; } ret = max(ret, *max_element(even.begin(), even.end()) * 2); return ret; } template <typename T, typename S> bool chmin(T &a, S b) { if (a > b) { a = b; return 1; } return 0; } bool is_pal(string s) { return s == string(s.rbegin(), s.rend()); } void solve() { int n, m; string s; cin >> n >> m >> s; if (max_pal_len(s) >= m) { cout << 1 << '\n'; return; } string ss = s + s; if (max_pal_len(ss) >= m) { cout << 2 << '\n'; return; } string sss = s + s + s; if (max_pal_len(sss) >= m) { cout << 3 << '\n'; return; } if (is_pal(s)) { cout << ceil_div(m, n) << '\n'; return; } string ttt = sss; reverse(ttt.begin(), ttt.end()); RollingHash sh(sss), th(ttt); int len = sss.size(); auto is_pal_substr = [&](int l, int r) { return sh.get(l, r) == th.get(len - r, len - l); }; auto ok = [&](int li, int ri) { if (ri >= n) return false; return is_pal_substr(li, ri + n + n + 1); }; int ans = 2e9; rep(midl, 0, n) { if (ok(midl, midl)) { int need = ceil_div(m - 1, 2); int tmp = 1; tmp += ceil_div(need - midl, (ll)n); tmp += ceil_div(need - (n - 1 - midl), (ll)n); chmin(ans, tmp); } if (ok(midl, midl + 1)) { int need = ceil_div(m - 2, 2); int tmp = 1; tmp += ceil_div(need - midl, (ll)n); tmp += ceil_div(need - (n - 2 - midl), (ll)n); chmin(ans, tmp); } } cout << (ans == 2e9 ? -1 : ans) << '\n'; } int main() { int t; cin >> t; while (t--) solve(); }