結果

問題 No.2858 Make a Palindrome
ユーザー ku_senjanku_senjan
提出日時 2024-08-25 16:04:55
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,437 bytes
コンパイル時間 4,173 ms
コンパイル使用メモリ 284,552 KB
実行使用メモリ 55,392 KB
最終ジャッジ日時 2024-08-25 16:05:03
合計ジャッジ時間 8,141 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 AC 88 ms
6,944 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 42 ms
48,388 KB
testcase_21 AC 42 ms
49,664 KB
testcase_22 AC 27 ms
27,420 KB
testcase_23 AC 42 ms
48,572 KB
testcase_24 AC 38 ms
43,280 KB
testcase_25 WA -
testcase_26 AC 33 ms
36,620 KB
testcase_27 WA -
testcase_28 AC 39 ms
41,176 KB
testcase_29 AC 43 ms
50,584 KB
testcase_30 WA -
testcase_31 AC 46 ms
55,068 KB
testcase_32 AC 46 ms
55,116 KB
testcase_33 AC 47 ms
55,160 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 52 ms
55,064 KB
testcase_37 AC 45 ms
55,280 KB
testcase_38 WA -
testcase_39 WA -
権限があれば一括ダウンロードができます

ソースコード

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{
		return ((r-1)/N) - (l/N) + 1;
	};

	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