oj.uz

답안 #917770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917770 2024-01-28T18:37:30 Z HaciyevAlik Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9+7,P=47,mx=1e6+5;
ll h[mx],p[mx];
string s;
bool check(int a,int b,int l) {
	ll h1=h[a+l-1]-h[a-1];
	ll h2=h[b+l-1]-h[b-1];
	return 1LL*h1*p[b-a]%mod == h2;
}
void solve() {
	cin >> s;
	int n=int(s.size());
	p[0]=1;
	for(int i=1;i<=n;++i) {	
		p[i]=(p[i-1]*P)%mod;
	}
	for(int i=1;i<=n;++i) {
		h[i]=(h[i-1]+(s[i-1]-'a'+1)*p[i-1])%mod;
		h[i]%=mod;
	}
	int l=1,r=n,res=0;
	while(l<=r) {
		int k=1;
		while(!check(l,r-k+1,k)) {
			++k;
		}
		l+=k,r-=k;
		res+=2;
	}
	cout << res-1;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--) {
		solve();
		cout << '\n';
	}
	return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -