oj.uz

Submission #140859

# Submission time Handle Problem Language Result Execution time Memory
140859 2019-08-05T19:59:14 Z hosseinmasoody Palinilap (COI16_palinilap) C++14
0 / 100
 96 ms 9468 KB 
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define MP make_pair
#define pii pair<int, int>
#define int long long
using namespace std;

const ll MX=2e5+5, del=1e9+7;

ll n, p=29, pbase[MX], h1[MX], h2[MX], arr[MX], ans[MX], ps[MX], cnt[MX], ANS, yek=1;

string s;

vector<pii>vec;

void HASH(){
	for(int i=1;i<=n;i++) h1[i]=(h1[i-1]*p+arr[i])%del;
	for(int i=n;i>=1;i--) h2[i]=(h2[i+1]*p+arr[i])%del;
}

int gethash(int l, int r, bool tp){
	int ans=0;
	if(tp==0){
		ans=(h1[r]-(pbase[r-l+1]*h1[l-1]%del)+del)%del;
	}
	else{
		ans=(h2[l]-(pbase[r-l+1]*h2[r+1]%del)+del)%del;
	}
	return ans;
}

bool ispal(int l, int r){
	if(l>=r) return true;
	if(l<=0 || l>n) return false;
	if(gethash(l, r, 0)==gethash(l, r, 1)) return true;
	return false;
}

bool ispal2(int l, int r, int R){
	if(l>=r) return true;
	if(l<=0 || l>n) return false;
	if(gethash(l, r, 0)==gethash(R, R+(l-r), 1)) return true;
	return false;
}

int32_t main(){
	pbase[0]=1;
	for(int i=1;i<MX;i++){
		pbase[i]=pbase[i-1]*p%del;
	}
	cin>>s;
	n=s.size();
	for(int i=0;i<n;i++){
		arr[i+1]=s[i]-'a'+1;
	}
	HASH();
	//cout<<ispal(2, 6)<<endl;
	for(int i=2;i<=2*n;i++){
		int lo=-1, hi=2*MX;
		while(hi-lo>1){
			int mid=(hi+lo)/2;
			//cout<<mid<<" "<<i-mid<<" "<<ispal(mid, i-mid)<<endl;
			if(ispal(mid, i-mid)){
				hi=mid;
			}
			else{
				lo=mid;
			}
		}
		//cout<<i<<" "<<hi<<endl;
		int l=hi, r=i-hi;
		if(l>r){
			//cout<<l<<endl;
		//	ans[l]=max(ans[l], yek), ans[r]=max(ans[r], yek);
			continue;
		}
		
		ANS+=(r-l)/2+1;
		
		vec.pb(MP(l, r));
		if(l==1 || r==n) continue;
		if(l==2 || r==n-1){
			if(ans[l-1]==0) ans[l-1]=1;
			if(ans[r+1]==0) ans[r+1]=1;
			continue;
		}
		if(arr[l-2]!=arr[r+2]){
			if(ans[l-1]==0) ans[l-1]=1;
			if(ans[r+1]==0) ans[r+1]=1;
			continue;
		}
		lo=-1, hi=2*MX;
		while(hi-lo>1){
			int mid=(hi+lo)/2;
			if(ispal2(mid, l-2, r+2)){
				hi=mid;
			}
			else{
				lo=mid;
			}
		}
		int temp=l-hi;
		ans[l-1]=max(ans[l-1], temp), ans[r+1]=max(ans[r+1], temp);
	}
	//cout<<ans[2]<<endl;
	for(int i=0;i<vec.size();i++){
		int l=vec[i].F, r=vec[i].S;
		cnt[l]++, cnt[r+1]--;
		ps[l]+=l-1;
		ps[r+1]-=(l-1);
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=ps[i];
		ANS=max(ANS, ANS+ans[i]-cnt[i]*i-sum);
	}
	if(n==1) return cout<<1<<endl, 0;
	cout<<max(ANS, n+1)<<endl;
	return 0;
}

Compilation message

palinilap.cpp: In function 'int32_t main()':
palinilap.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++){
              ~^~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 9468 KB Output isn't correct
2 Halted 0 ms 0 KB -