oj.uz

Submission #917787

# Submission time Handle Problem Language Result Execution time Memory
917787 2024-01-28T19:26:23 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 97 ms 17140 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 8796 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8792 KB Output is correct
4 Correct 6 ms 8796 KB Output is correct
5 Correct 6 ms 8796 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8796 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8792 KB Output is correct
4 Correct 6 ms 8796 KB Output is correct
5 Correct 6 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 8792 KB Output is correct
9 Correct 6 ms 8836 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8796 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8792 KB Output is correct
4 Correct 6 ms 8796 KB Output is correct
5 Correct 6 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 8792 KB Output is correct
9 Correct 6 ms 8836 KB Output is correct
10 Correct 7 ms 8792 KB Output is correct
11 Correct 7 ms 8796 KB Output is correct
12 Correct 7 ms 8836 KB Output is correct
13 Correct 7 ms 8796 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8796 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 6 ms 8792 KB Output is correct
4 Correct 6 ms 8796 KB Output is correct
5 Correct 6 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 8792 KB Output is correct
9 Correct 6 ms 8836 KB Output is correct
10 Correct 7 ms 8792 KB Output is correct
11 Correct 7 ms 8796 KB Output is correct
12 Correct 7 ms 8836 KB Output is correct
13 Correct 7 ms 8796 KB Output is correct
14 Correct 97 ms 17140 KB Output is correct
15 Correct 55 ms 17132 KB Output is correct
16 Correct 90 ms 17132 KB Output is correct
17 Correct 52 ms 13560 KB Output is correct