제출 #99239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99239		dsg213	Palinilap (COI16_palinilap)	C++14	54 / 100	109 ms	32108 KiB

palinilap

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
const int mod=1000000007,mxn=1000010;
string s;
int n;
ull p=313;
ull hap[mxn];
ull hal[mxn];
ull pot[mxn];
ull gethp(int left,int right){
	return hap[right]-hap[left-1]*pot[right-left+1];
}
ull gethl(int left,int right){
	return hal[left]-hal[right+1]*pot[right-left+1];
}
ll acc[mxn];
ll ilz[mxn];
ll wie[mxn][26];
ll ans;
void liczsro(int x){
	int mn=1;
	int mx=min(x,n-x+1);
	////cout <<mx <<" ";
	while(mn<mx){
		int sr=(mn+mx+1)/2;
		if(gethp(x-sr+1,x)==gethl(x,x+sr-1)){
			mn=sr;
		}
		else{
			mx=sr-1;
		}
	}
	////cout <<mn <<" ";
	acc[x-mn]+=1;
	acc[x]-=2;
	acc[x+mn]+=1;
	ilz[x]-=mn;
	int baz=mn;
	ans+=baz;
	if(baz==min(x,n-x+1)){
		////cout <<"0\n";
		return;
	}
	mx=min(x,n-x+1);
	mn=baz+1;
	while(mn<mx){
		int sr=(mn+mx+1)/2;
		if(gethp(x-sr+1,x-baz-1) == gethl(x+baz+1,x+sr-1)){
			mn=sr;
		}
		else{
			mx=sr-1;
		}
	}
	int dod=mn-baz;
	////cout <<baz <<" "<<dod <<"\n";
	char c1=s[x-baz-1]-'a';
	char c2=s[x+baz-1]-'a';
	wie[x-baz][c2]+=dod;
	wie[x+baz][c1]+=dod;
	////cout <<x  <<" " <<baz <<" " <<c2+'a' <<"\n";
}
void liczd(int x){
	int mn=0;
	int mx=min(x,n-x);
	while(mn<mx){
		int sr=(mn+mx+1)/2;
		if(gethp(x-sr+1,x)==gethl(x+1,x+sr)){
			mn=sr;
		}
		else{
			mx=sr-1;
		}
	}
	////cout <<mn <<" ";
	acc[x-mn]+=1;
	acc[x]-=1;
	acc[x+1]-=1;
	acc[x+mn+1]+=1;
	//ilz[x]-=mn;
	int baz=mn;
	ans+=baz;
	if(baz==min(x,n-x)){
		////cout <<"0 ";
		return;
	}
	mx=min(x,n-x);
	mn=baz+1;
	////cout <<mx <<" ";
	while(mn<mx){
		int sr=(mn+mx+1)/2;
		if(gethp(x-sr+1,x-baz-1) == gethl(x+baz+2,x+sr)){
			mn=sr;
		}
		else{
			mx=sr-1;
		}
	}
	int dod=mn-baz;
	////cout <<dod <<" ";
	char c1=s[x-baz-1]-'a';
	char c2=s[x+baz]-'a';
	wie[x-baz][c2]+=dod;
	wie[x+baz+1][c1]+=dod;
	////cout <<x-baz <<" " <<'a'+c2 <<"\n";
}
void pro(){
	ll pr=0;
	ll val=0;
	for(int i=0;i<=n;i++){
		ilz[i]+=val;
		pr+=acc[i];
		val+=pr;
	}
}
int main(){
	cin >>s;
	n=s.size();
	pot[0]=1;
	for(ull i=1;i<=mxn-10;i++){
		pot[i]=pot[i-1]*p;
	}
	for(int i=0;i<n;i++){
		hap[i+1]=hap[i]*p+s[i];
	}
	for(int i=n;i>0;i--){
		hal[i]=hal[i+1]*p+s[i-1];
	}
	/*while(1){
		int a,b;
		cin >>a >>b;
		//cout <<gethp(a,b) <<"\n";
		//cout <<gethl(a,b) <<"\n";
	}*/
	for(int i=1;i<=n;i++){
		liczsro(i);
	}
	////cout <<"\n";
	for(int i=1;i<n;i++){
		liczd(i);
	}
	////cout <<"\n";
	pro();
	////cout <<"\n";
	/*for(int i=0;i<=n;i++){
		//cout <<acc[i] <<" ";
	}
	//cout <<"\n";
	*/
	/*for(int i=0;i<=n;i++){
		//cout <<ilz[i] <<" ";
	}*/
	//cout <<ans<<"\n";
	ll wyn=ans;
	for(int i=1;i<=n;i++){
		//cout <<ilz[i] <<" "; 
		for(int j=0;j<26;j++){
			wyn=max(wyn,ans+wie[i][j]-ilz[i]);
		}
	}
	//cout <<"\n";
	for(int i=1;i<=n;i++){
		ll x=0;
		for(int j=0;j<26;j++){
			x=max(x,wie[i][j]);
		}
		//cout <<x<<" ";
	}
	//cout <<"\n";
	cout <<wyn;
}

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

palinilap.cpp: In function 'void liczsro(int)':
palinilap.cpp:68:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x-baz][c2]+=dod;
               ^
palinilap.cpp:69:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x+baz][c1]+=dod;
               ^
palinilap.cpp: In function 'void liczd(int)':
palinilap.cpp:112:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x-baz][c2]+=dod;
               ^
palinilap.cpp:113:17: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x+baz+1][c1]+=dod;
                 ^

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