結果
問題 | No.2858 Make a Palindrome |
ユーザー |
👑 ![]() |
提出日時 | 2024-08-25 16:02:08 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 503 ms / 3,000 ms |
コード長 | 6,833 bytes |
コンパイル時間 | 4,430 ms |
コンパイル使用メモリ | 242,372 KB |
実行使用メモリ | 58,616 KB |
最終ジャッジ日時 | 2024-08-25 16:02:19 |
合計ジャッジ時間 | 10,312 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#define ATCODER#define _USE_MATH_DEFINES#include <stdio.h>#include <iostream>#include <fstream>#include <algorithm>#include <vector>#include <string>#include <cassert>#include <numeric>#include <unordered_map>#include <unordered_set>#include <queue>#include <math.h>#include <climits>#include <set>#include <map>#include <list>#include <random>#include <iterator>#include <bitset>#include <chrono>#include <type_traits>using namespace std;using ll = long long;using ld = long double;using pll = pair<ll, ll>;using pdd = pair<ld, ld>;#define FOR(i, a, b) for (ll i = (a); i < (b); i++)#define REP(i, n) for (ll i = 0; i < (n); i++)#define ROF(i, a, b) for (ll i = (b - 1); i >= (a); i--)#define PER(i, n) for (ll i = n - 1; i >= 0; i--)#define VL vector<ll>#define VVL vector<vector<ll>>#define VP vector<pair<ll, ll>>#define LPQ(T) priority_queue<T, vector<T>, greater<T>>#define all(i) begin(i), end(i)#define SORT(i) sort(all(i))#define EXISTBIT(x, i) (((x >> i) & 1) != 0)#define CHMAX(n, v) n = n < v ? v : n#define CHMIN(n, v) n = n > v ? v : n#define MP(a, b) make_pair(a, b)#define DET2(x1, y1, x2, y2) (x1) * (y2) - (x2) * (y1)#define DET3(x1, y1, z1, x2, y2, z2, x3, y3, z3) (x1) * (y2) * (z3) + (x2) * (y3) * (z1) + (x3) * (y1) * (z2) - (z1) * (y2) * (x3) - (z2) * (y3) *(x1) - (z3) * (y1) * (x2)#define INC(a) \for (auto &v : a) \v++;#define DEC(a) \for (auto &v : a) \v--;#define SQU(x) (x) * (x)#ifdef ATCODER#include <atcoder/all>using namespace atcoder;using mint = modint1000000007;using mint2 = modint998244353;#endiftemplate <typename T = ll>vector<T> read(size_t n){vector<T> ts(n);for (size_t i = 0; i < n; i++)cin >> ts[i];return ts;}template <typename TV, const ll N>void read_tuple_impl(TV &) {}template <typename TV, const ll N, typename Head, typename... Tail>void read_tuple_impl(TV &ts){get<N>(ts).emplace_back(*(istream_iterator<Head>(cin)));read_tuple_impl<TV, N + 1, Tail...>(ts);}template <typename... Ts>decltype(auto) read_tuple(size_t n){tuple<vector<Ts>...> ts;for (size_t i = 0; i < n; i++)read_tuple_impl<decltype(ts), 0, Ts...>(ts);return ts;}using val = mint;using val2 = mint2;using func = ll;val op(val a, val b){return a*b;}val e() { return 1; }val2 op2(val2 a, val2 b){return a*b;}val2 e2() { return 1; }val mp(func f, val a){return a + f;}func comp(func f, func g){return f + g;}func id() { return 0; }ll di[4] = {1, 0, -1, 0};ll dj[4] = {0, 1, 0, -1};ll si[4] = {0, 3, 3, 0};ll sj[4] = {0, 0, 3, 3};// ll di[4] = { -1,-1,1,1 };// ll dj[4] = { -1,1,-1,1 };ll di8[8] = {0, -1, -1, -1, 0, 1, 1, 1};ll dj8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};struct PalindromicTree {//// private:struct node {map<char, int> link;int suffix_link;ll len;ll count;};vector<node> c;string s;int active_idx;node* create_node() {c.emplace_back();node* ret = &c.back();ret->count = 0;return ret;}// this->s の状態に依存するint find_prev_palindrome_idx(int node_id) {const int pos = int(s.size()) - 1;while (true) {const int opposite_side_idx = pos - 1 - c[node_id].len;if (opposite_side_idx >= 0 && s[opposite_side_idx] == s.back()) break;node_id = c[node_id].suffix_link; // 次の回文に移動}return node_id;}bool debug_id2string_dfs(int v, int id, vector<char>& charas) {if (v == id) return true;for (auto kv : c[v].link) {if (debug_id2string_dfs(kv.second, id, charas)) {charas.push_back(kv.first);return true;}}return false;}public:PalindromicTree() {node* size_m1 = create_node(); // 長さ-1のノードを作成size_m1->suffix_link = 0; // -1 の親suffixは自分自身size_m1->len = -1;node* size_0 = create_node(); // 長さ0のノードを作成size_0->suffix_link = 0; // 親は長さ-1のノードsize_0->len = 0;active_idx = 0;}int get_active_idx() const {return active_idx;}node* get_node(int id) {return &c[id];}void add(char ch) {s.push_back(ch);// ch + [A] + ch が回文となるものを探すconst int a = find_prev_palindrome_idx(active_idx);//新しいノードへのリンクが発生するか試すconst auto inserted_result = c[a].link.insert(make_pair(ch, int(c.size())));active_idx = inserted_result.first->second; // insertの成否に関わらず、iteratorが指す先は新しい回文のindexif (!inserted_result.second) {c[active_idx].count++; // その回文が現れた回数が増加return; // 既にリンクが存在したので、新しいノードを作る必要がない}// 実際に新しいノードを作成node* nnode = create_node();nnode->count = 1;nnode->len = c[a].len + 2; // ch + [A] + ch だから、長さは len(A) + 2// suffix_linkの設定if (nnode->len == 1) {// この時だけsuffix_linkはsize 0に伸ばすnnode->suffix_link = 1;}else {// ch + [B] + ch が回文になるものを探す。ただし長さはaより小さいものconst int b = find_prev_palindrome_idx(c[a].suffix_link);nnode->suffix_link = c[b].link[ch];}}//各文字列が何回現れるか計算する// O(n)vector<int> build_frequency() {vector<int> frequency(c.size());//常に親ノードのid < 子ノードのidが成り立つので、idを大きい順から回せばよいfor (int i = int(c.size()) - 1; i > 0; i--) {frequency[i] += c[i].count;frequency[c[i].suffix_link] += frequency[i];}return frequency;}};void solve(){ll n,m;cin>>n>>m;string s;cin>>s;PalindromicTree pt1,pt2;vector<bool> pal(n+1),rpal(n+1);pal[0]=true;rpal[n]=true;ll solo=0;ll duo=0;REP(i,n){pt1.add(s[i]);if(pt1.get_node(pt1.active_idx)->len==i+1){pal[i+1]=true;}CHMAX(solo,pt1.get_node(pt1.active_idx)->len);}REP(i,n){pt1.add(s[i]);CHMAX(duo,pt1.get_node(pt1.active_idx)->len);}PER(i,n){pt2.add(s[i]);if(pt2.get_node(pt2.active_idx)->len==n-i){rpal[i]=true;}}if(solo>=m){cout<<1<<endl;return;}if(duo>=m){cout<<2<<endl;return;}ll ans=1e18;REP(i,n+1){if(pal[i]&&rpal[i]){ll tmp=max(m/n - 10,0LL);while(1){if(tmp*n+i >=m || tmp*n+n-i>=m){CHMIN(ans,tmp+1);break;}tmp++;}}}if(ans>1e17)ans=-1;cout<<ans<<endl;return;}int main(){ll t = 1;cin >> t;while (t--){solve();}return 0;}