結果

問題 No.2858 Make a Palindrome
ユーザー ku_senjan
提出日時 2024-08-25 16:20:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,550 bytes
コンパイル時間 3,567 ms
コンパイル使用メモリ 286,404 KB
実行使用メモリ 55,256 KB
最終ジャッジ日時 2024-08-25 16:20:54
合計ジャッジ時間 7,254 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 WA * 22 RE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr ll INF = 1LL<<60;

class RollingHash{
	using ll = long long;

	private:
		static const ll mod1=888888901, mod2=987654323;
		ll base1, base2;
		int n;
		vector<ll> hash1, hash2, pow1, pow2;

	public:
		RollingHash(const string &s, const ll _base1=2525, const ll _base2=4649):
			base1(_base1), base2(_base2) {
				n = s.length();
				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;
				}
			}

		pair<ll,ll> get(const int l, const int r) const{
			ll fi = hash1[r]-(hash1[l]*pow1[r-l]%mod1);
			if(fi<0) fi += mod1;
			ll se = hash2[r]-(hash2[l]*pow2[r-l]%mod2);
			if(se<0) se += mod2;
			return make_pair(fi,se);
		}

		pair<ll,ll> merge(const pair<ll,ll> a, const pair<ll,ll> b, const int b_len) const{
			ll fi = ((a.first*pow1[b_len])%mod1 + b.first) % mod1;
			ll se = ((a.second*pow2[b_len])%mod2 + b.second) % mod2;
			return make_pair(fi, se);
		}
};

void solve(){
	int N;
	cin >> N;
	ll M;
	cin >> M;
	string S;
	cin >> S;

	string s = S+S+S+S;
	string r = s;
	reverse(r.begin(), r.end());

	RollingHash a(s), b(r);
	auto get_a = [&](int l, int r) -> pair<ll,ll>{
		return a.get(l+(N*2), r+(N*2));
	};
	auto get_b = [&](int l, int r) -> pair<ll,ll>{
		return b.get((N*2)-r, (N*2)-l);
	};

	auto cnt = [&](ll l, ll r) -> ll{
		if(l<0){
			l = -(abs(l+1)/N+1);
		}else{
			l = l/N;
		}
		if(r<0){
			r = -(abs(r+1)/N+1);
		}else{
			r = r/N;
		}

		return r-l;
	};

	ll ans = INF;

	// even
	if((M+1)/2<=N){
		ll len = (M+1)/2;
		for(int i=0; i<N; i++){
			if(get_a(i-len, i)==get_b(i, i+len)){
				ans = min(ans, cnt(i-len, i+len));
			}
		}
	}else{
		ll len = N;
		ll rep = (M+N*2-1)/(N*2);
		for(int i=0; i<N; i++){
			if(get_a(i-len, i)==get_b(i, i+len)){
				ans = min(ans, cnt(i-len*rep, i+len*rep));
			}
		}
	}
	
	// odd
	if(M/2<=N-1){
		ll len = M/2;
		for(int i=0; i<N; i++){
			if(get_a(i-len, i)==get_b(i+1, i+1+len)){
				ans = min(ans, cnt(i-len, i+1+len));
			}
		}
	}else{
		ll len = N-1;
		ll rep = (M+(N-1)*2-1)/((N-1)*2);
		for(int i=0; i<N; i++){
			if(get_a(i-len, i)==get_b(i+1, i+1+len)){
				ans = min(ans, cnt(i-len*rep, (i+1)+len*rep));
			}
		}
	}

	if(ans==INF) cout << -1 << endl;
	else cout << ans << endl;
}

int main(){
	int T;
	cin >> T;
	for(;T--;) solve();

	return 0;
}
0