oj.uz

Submission #748646

# Submission time Handle Problem Language Result Execution time Memory
748646 2023-05-26T16:53:03 Z mariowong Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 1934 ms 19032 KB 
#include <bits/stdc++.h>
#define hmod (long long)99999989
using namespace std;
 
int t,n,l,r,anss;
long long a[1000005],sum;
string s;
long long fpow(long long a,long long b){
	long long ans=1,base=a;
	while (b > 0){
		if ((b&1) == 1) ans=ans*base%hmod;
		base=base*base%hmod;
		b/=2;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> t;
	while (t--){
		cin >> s; n=s.length();
		sum=1;
		for (int i=0;i<n;i++){
			a[i]=(s[i]-'a')*sum;
			a[i]+=a[i-1];
			a[i]%=hmod;
			sum*=26; sum%=hmod;
		}
		l=0; r=n-1; anss=0;
		for (int i=0;i<n;i++){
			if (r-(i-l+1)+1 <= i){
				if (l <= r)
				anss++;
				break;
			}
			if (l == 0 && 
			((a[i]+hmod)%hmod*fpow(fpow(26,hmod-2),l))%hmod == 
			    ((a[r]-a[r-(i-l+1)]+hmod)%hmod*fpow(fpow(26,hmod-2),r-(i-l+1)+1))%hmod
			){
			    anss+=2;
				r=r-(i-l+1);
			    l=i+1;	
			}
			else
			if (l != 0 &&
				((a[i]-a[l-1]+hmod)%hmod*fpow(fpow(26,hmod-2),l))%hmod == 
			    ((a[r]-a[r-(i-l+1)]+hmod)%hmod*fpow(fpow(26,hmod-2),r-(i-l+1)+1))%hmod
				){
			    anss+=2;
				r=r-(i-l+1);
			    l=i+1;	
			}
		}
		cout << anss << "\n";
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 232 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 232 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 232 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 16 ms 468 KB Output is correct
11 Correct 8 ms 468 KB Output is correct
12 Correct 18 ms 472 KB Output is correct
13 Correct 16 ms 420 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 232 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 16 ms 468 KB Output is correct
11 Correct 8 ms 468 KB Output is correct
12 Correct 18 ms 472 KB Output is correct
13 Correct 16 ms 420 KB Output is correct
14 Correct 1784 ms 19032 KB Output is correct
15 Correct 767 ms 14364 KB Output is correct
16 Correct 1934 ms 18436 KB Output is correct
17 Correct 1103 ms 10304 KB Output is correct