제출 #140862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
140862		hosseinmasoody	Palinilap (COI16_palinilap)	C++14	0 / 100	102 ms	9516 KiB

palinilap

#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(r>=l) ANS+=(r-l)/2+1;
		
		if(r>=l) 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<<endl;
	//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;
	int TANS=ANS;
	for(int i=1;i<=n;i++){
		sum+=ps[i];
		ANS=max(ANS, TANS+ans[i]-cnt[i]*i-sum+1);
	}
	cout<<ANS;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46