結果

問題 No.2858 Make a Palindrome
ユーザー 👑 amentorimaru
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
#endif
template <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; // insertiteratorindex
if (!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_linksize 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 < idid
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0