結果
問題 | No.2858 Make a Palindrome |
ユーザー | shinchan |
提出日時 | 2024-08-25 16:16:06 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,833 bytes |
コンパイル時間 | 2,223 ms |
コンパイル使用メモリ | 210,492 KB |
実行使用メモリ | 67,840 KB |
最終ジャッジ日時 | 2024-08-25 16:16:13 |
合計ジャッジ時間 | 6,887 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 406 ms
6,816 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 64 ms
6,944 KB |
testcase_11 | AC | 64 ms
6,940 KB |
testcase_12 | AC | 63 ms
6,944 KB |
testcase_13 | AC | 63 ms
6,940 KB |
testcase_14 | AC | 62 ms
6,944 KB |
testcase_15 | AC | 50 ms
6,940 KB |
testcase_16 | AC | 54 ms
6,940 KB |
testcase_17 | AC | 55 ms
6,940 KB |
testcase_18 | AC | 54 ms
6,944 KB |
testcase_19 | AC | 51 ms
6,940 KB |
testcase_20 | AC | 48 ms
59,484 KB |
testcase_21 | AC | 49 ms
60,872 KB |
testcase_22 | AC | 29 ms
33,328 KB |
testcase_23 | AC | 48 ms
59,444 KB |
testcase_24 | AC | 43 ms
52,720 KB |
testcase_25 | AC | 40 ms
46,816 KB |
testcase_26 | AC | 37 ms
44,776 KB |
testcase_27 | AC | 54 ms
67,032 KB |
testcase_28 | AC | 43 ms
49,468 KB |
testcase_29 | AC | 49 ms
62,168 KB |
testcase_30 | AC | 54 ms
67,840 KB |
testcase_31 | AC | 53 ms
67,816 KB |
testcase_32 | AC | 54 ms
67,704 KB |
testcase_33 | AC | 53 ms
67,708 KB |
testcase_34 | AC | 51 ms
67,808 KB |
testcase_35 | AC | 52 ms
67,712 KB |
testcase_36 | AC | 51 ms
67,700 KB |
testcase_37 | AC | 55 ms
67,832 KB |
testcase_38 | AC | 52 ms
67,660 KB |
testcase_39 | AC | 54 ms
67,812 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(),(v).end() #define pb(a) push_back(a) #define rep(i, n) for(int i=0;i<n;i++) #define foa(e, v) for(auto& e : v) using ll = long long; const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60); #define dout(a) cout<<fixed<<setprecision(10)<<a<<endl; struct RollingHash { static const int base1 = 1007, base2 = 2009; static const int mod1 = 998244353, mod2 = 1000000009; std::vector<long long> hash1, hash2, power1, power2; std::vector<long long> hash1_, hash2_, power1_, power2_; void rev_init(std::string S) { std::reverse(S.begin(), S.end()); int n = (int)S.size(); hash1_.assign(n+1, 0); hash2_.assign(n+1, 0); power1_.assign(n+1, 1); power2_.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; power1_[i+1] = (power1_[i] * base1) % mod1; power2_[i+1] = (power2_[i] * base2) % mod2; } } // construct RollingHash(const std::string &S, int rev = 0) { int n = (int)S.size(); hash1.assign(n+1, 0); hash2.assign(n+1, 0); power1.assign(n+1, 1); power2.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; power1[i+1] = (power1[i] * base1) % mod1; power2[i+1] = (power2[i] * base2) % mod2; } if(rev) rev_init(S); } // get hash of S[left:right) inline std::pair<long long, long long> get(int l, int r) const { long long res1 = hash1[r] - hash1[l] * power1[r-l] % mod1; if (res1 < 0) res1 += mod1; long long res2 = hash2[r] - hash2[l] * power2[r-l] % mod2; if (res2 < 0) res2 += mod2; return {res1, res2}; } inline std::pair<long long, long long> get_rev(int l, int r) const { long long res1 = hash1_[r] - hash1_[l] * power1_[r-l] % mod1; if (res1 < 0) res1 += mod1; long long res2 = hash2_[r] - hash2_[l] * power2_[r-l] % mod2; if (res2 < 0) res2 += mod2; return {res1, res2}; } // [l, r) is palindrome inline bool is_palindrome(int l, int r, int n) const { int l_rev = n - r; int r_rev = n - l; return get(l, r) == get_rev(l_rev, r_rev); } // get lcp of S[a:) and T[b:) inline int getLCP(int a, int b) const { int len = std::min((int)hash1.size()-a, (int)hash1.size()-b); int low = -1, high = len; while (high - low > 1) { int mid = (low + high) / 2; if (get(a, a+mid) != get(b, b+mid)) high = mid; else low = mid; } return low; } }; void solve() { ll n, m; string s; cin >> n >> m >> s; string u = ""; for(int k = 1; k <= 10; k ++) { int sz = n * k; if(sz < m) break; u += s; RollingHash r(u, 1); bool ok = 0; rep(i, sz - m + 1) { if(r.is_palindrome(i, i + m, sz)) { ok = true; break; } } if(ok) { cout << k << endl; return; } } ll ans = INF; s = s + s + s + s + s; int sz = s.size(); RollingHash r(s, 1); { ll k = (m + 1) / 2; for(int i = n * 2; i < n * 3; i ++) { ll num = min(i, sz - i); if(r.is_palindrome(i - num, i + num, sz)) { ll val = 1; ll ri = sz - i - n * 2; if(k > ri) { ll r = k - ri; val += (r + n - 1) / n; } ll le = i - n * 2; if(k > le) { ll l = k - le; val += (l + n - 1) / n; } ans = min(ans, val); } } } { ll k = m / 2; for(int i = n * 2; i < n * 3; i ++) { ll num = min(i, sz - i - 1); if(r.is_palindrome(i - num, i + num + 1, sz)) { ll val = 1; ll ri = sz - i - 1 - n * 2; if(k > ri) { ll r = k - ri; val += (r + n - 1) / n; } ll le = i - n * 2; if(k > le) { ll l = k - le; val += (l + n - 1) / n; } ans = min(ans, val); } } } cout << (ans == INF ? -1 : ans) << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); int t; cin >> t; rep(i, t) solve(); return 0; }