結果

問題 No.2858 Make a Palindrome
ユーザー ku_senjanku_senjan
提出日時 2024-08-25 16:22:05
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,530 bytes
コンパイル時間 3,736 ms
コンパイル使用メモリ 285,516 KB
実行使用メモリ 81,168 KB
最終ジャッジ日時 2024-08-25 16:22:13
合計ジャッジ時間 7,892 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 WA -
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 52 ms
70,840 KB
testcase_21 AC 53 ms
72,720 KB
testcase_22 AC 32 ms
39,312 KB
testcase_23 AC 51 ms
70,964 KB
testcase_24 AC 49 ms
63,228 KB
testcase_25 WA -
testcase_26 AC 38 ms
53,140 KB
testcase_27 WA -
testcase_28 AC 47 ms
59,544 KB
testcase_29 AC 52 ms
74,148 KB
testcase_30 WA -
testcase_31 AC 56 ms
80,880 KB
testcase_32 AC 56 ms
80,860 KB
testcase_33 AC 57 ms
80,972 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 57 ms
80,828 KB
testcase_37 AC 55 ms
80,876 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{
	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+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*3), r+(N*3));
	};
	auto get_b = [&](int l, int r) -> pair<ll,ll>{
		return b.get((N*3)-r, (N*3)-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