oj.uz

Submission #499689

# Submission time Handle Problem Language Result Execution time Memory
499689 2021-12-29T08:51:35 Z codr0 Palindromic Partitions (CEOI17_palindromic) C++14
15 / 100
 7 ms 332 KB 
#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
 
using namespace std;
const int N=1e6+5;
const int MOD1=98765431;
const int MOD2=1000696969;
int n;
int ps1[N],ps2[N];
int PW1[N],PW2[N];
int ans[N];
string s;
const int M=31;
	
	int pw(int a,int b,int MOD){
		if(!b) return 1;
		int rt=pw(a,b/2,MOD);
		rt=(rt*rt)%MOD;
		if(b&1) rt=(rt*a)%MOD;
		return rt;
	}

	int inv(int x,int MOD){
		return pw(x,MOD-2,MOD);
	}
	
	int f(int x){
		if(ans[x]==-1){
		
		int l=1+x;int r=n-x;
		if(r==l) {ans[x]=1; return ans[x];}
		else if(r<l) {ans[x]=0; return ans[x];}
		else if((l+1)==r) {ans[x]=(s[l]==s[r])+1; return ans[x];}
		ans[x]=0;
		int t=-1;
		while(1){
			int mid1=(r+l)/2;
			int mid2=mid1+1;
			if((r-l+1)&1)	mid1--;
			FOR(i,0,mid1-l){
				int hsh1m=ps1[i+l]-ps1[l-1];
				hsh1m=hsh1m*inv(PW1[l-1],MOD1); hsh1m=((hsh1m%MOD1)+MOD1)%MOD1;
				int hsh2m=ps1[r]-ps1[r-i-1];
				hsh2m=hsh2m*inv(PW1[r-i-1],MOD1); hsh2m=((hsh2m%MOD1)+MOD1)%MOD1;
				
				int hsh1p=ps2[i+l]-ps2[l-1];
				hsh1p=hsh1p*inv(PW2[l-1],MOD2); hsh1p=((hsh1p%MOD2)+MOD2)%MOD2;
				int hsh2p=ps2[r]-ps2[r-i-1];
				hsh2p=hsh2p*inv(PW2[r-i-1],MOD2); hsh2p=((hsh2p%MOD2)+MOD2)%MOD2;

				if(hsh1m==hsh2m&&hsh1p==hsh2p) {t=i; break;}
			}
			break;
		}
		if(t==-1) {
			ans[x]=1;
			return ans[x];
		}else{
			int mid1=(r+l)/2;
			int mid2=mid1+1;
			if((r-l+1)&1)	mid1--;

			FOR(i,t,min(mid1-l,2*t+3)){
				int hsh1m=ps1[i+l]-ps1[l-1];
				hsh1m=hsh1m*inv(PW1[l-1],MOD1); hsh1m=((hsh1m%MOD1)+MOD1)%MOD1;
				int hsh2m=ps1[r]-ps1[r-i-1];
				hsh2m=hsh2m*inv(PW1[r-i-1],MOD1); hsh2m=((hsh2m%MOD1)+MOD1)%MOD1;
				
				int hsh1p=ps2[i+l]-ps2[l-1];
				hsh1p=hsh1p*inv(PW2[l-1],MOD2); hsh1p=((hsh1p%MOD2)+MOD2)%MOD2;
				int hsh2p=ps2[r]-ps2[r-i-1];
				hsh2p=hsh2p*inv(PW2[r-i-1],MOD2); hsh2p=((hsh2p%MOD2)+MOD2)%MOD2;

				if(hsh1m==hsh2m&&hsh1p==hsh2p) ans[x]=max(ans[x],f(x+i+1)+2);
			}
		}
		}
		return ans[x];
	}

	void Main(){
		cin>>s; n=SZ(s); s='$'+s;
		FOR(i,0,2*n) ans[i]=-1;
		
		ps1[0]=0;
		PW1[0]=1;
		FOR(i,1,n) PW1[i]=(PW1[i-1]*M)%MOD1;
		FOR(i,1,n){
			ps1[i]=ps1[i-1];
			ps1[i]+=((s[i]-'a'+1)*PW1[i-1])%MOD1;
		}

		ps2[0]=0;
		PW2[0]=1;
		FOR(i,1,n) PW2[i]=(PW2[i-1]*M)%MOD2;
		FOR(i,1,n){
			ps2[i]=ps2[i-1];
			ps2[i]+=((s[i]-'a'+1)*PW2[i-1])%MOD2;
		}

		cout<<f(0)<<'\n';
		
	}

	int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int T; cin>>T;
	while(T--) Main();

	return 0;
    }

Compilation message

palindromic.cpp: In function 'long long int f(long long int)':
palindromic.cpp:46:8: warning: unused variable 'mid2' [-Wunused-variable]
   46 |    int mid2=mid1+1;
      |        ^~~~
palindromic.cpp:68:8: warning: unused variable 'mid2' [-Wunused-variable]
   68 |    int mid2=mid1+1;
      |        ^~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 7 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 7 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 7 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -