oj.uz

Submission #917786

# Submission time Handle Problem Language Result Execution time Memory
917786 2024-01-28T19:25:19 Z HaciyevAlik Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 102 ms 17396 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7,P=47,mx=1e6+5;
ll h[mx],p[mx];
string s;
bool check(ll a,ll b,ll l) {
	if(a>b) return false;
	ll h1=(h[a+l-1]-h[a-1]+mod)%mod;
	ll h2=(h[b+l-1]-h[b-1]+mod)%mod;
	return h1*p[b-a]%mod == h2;
}
void solve() {
	cin >> s;
	ll n=ll(s.size());
	for(ll i=1;i<=n;++i) {
		h[i]=(h[i-1]+(s[i-1]-'a'+1)*p[i-1])%mod;
		h[i]%=mod;
	}
	ll l=1,r=n,res=0;
	while(l<=r) {	
		ll k=1;
		while(!check(l,r-k+1,k)) {
			++k;
		}
		if(l==r-k+1) {
			++res;
			break;
		}
		l+=k,r-=k;
		res+=2;
	}
	cout << res;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	p[0]=1;
	for(ll i=1;i<mx;++i) {
		p[i]=(p[i-1]*P)%mod;
	}
	ll t; cin >> t;
	while(t--) {
		solve();
		cout << '\n';
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8792 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 6 ms 8840 KB Output is correct
5 Correct 7 ms 8796 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8792 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 6 ms 8840 KB Output is correct
5 Correct 7 ms 8796 KB Output is correct
6 Correct 6 ms 8796 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 6 ms 8840 KB Output is correct
9 Correct 7 ms 8796 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8792 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 6 ms 8840 KB Output is correct
5 Correct 7 ms 8796 KB Output is correct
6 Correct 6 ms 8796 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 6 ms 8840 KB Output is correct
9 Correct 7 ms 8796 KB Output is correct
10 Correct 7 ms 8796 KB Output is correct
11 Correct 7 ms 8792 KB Output is correct
12 Correct 7 ms 8792 KB Output is correct
13 Correct 7 ms 8832 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8792 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8796 KB Output is correct
4 Correct 6 ms 8840 KB Output is correct
5 Correct 7 ms 8796 KB Output is correct
6 Correct 6 ms 8796 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 6 ms 8840 KB Output is correct
9 Correct 7 ms 8796 KB Output is correct
10 Correct 7 ms 8796 KB Output is correct
11 Correct 7 ms 8792 KB Output is correct
12 Correct 7 ms 8792 KB Output is correct
13 Correct 7 ms 8832 KB Output is correct
14 Correct 102 ms 17396 KB Output is correct
15 Correct 59 ms 17040 KB Output is correct
16 Correct 90 ms 17136 KB Output is correct
17 Correct 53 ms 13560 KB Output is correct