Submission #111518

#	Time	Username	Problem	Language	Result	Execution time	Memory
111518		dndhk	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	1690 ms	18664 KiB

palindromic

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll P1 = 317;
const ll P2 = 331;
const ll DIV = 1000000007;

int T;
string str;

const int MAX_N = 1000000;
long long str1, str2;
ll arr[MAX_N+1];

ll pw(ll x, ll y){
	if(y==0)	return 1;
	if(y==1)	return x;
	ll m = pw(x, y/2);
	if(y%2){
		return (((m*m)%DIV) * x) % DIV;
	}else{
		return (m*m) % DIV;
	}
}

bool chk(int x1, int x2, int y1, int y2){
	if(y2-y1!=x2-x1)	return false;
	for(int i=0; i<=x2-x1; i++){
		if(str[x1+i]!=str[y1+i])	return false;
	}
	return true;
}

ll p[30] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113};

int calc(){
	int x, y;
	x = 0; y = str.size()-1;
	int ans = 0;
	while(1){
		if(x>y)	return ans;
		if(x==y)	return ans+1;
		ll num1 = 0, num2 = 0;
		int l = 1;
		while(1){
			if(x+l-1 > y-l+1){
				return ans+1;
			}
			num1 = ((num1 * P1) + p[str[x+l-1] - 'a']) % DIV;
			num2 = ((num2 * P2) + p[str[x+l-1] - 'a']) % DIV;
			if((str1 + num1 * pw(P1, x))%DIV==arr[x+l]){
				if(!chk(x, x+l-1, y-l+1, y))	continue;
				str1 = (str1 + num1 * pw(P1, x))%DIV;
				str2 = (str2 + num2 * pw(P2, x))%DIV;
				ans += 2;
				x = x+l; y = y-l;
				break;
			}
			l++;
		}
	}
}

int main(){
	cin>>T;
	while(T--){
		cin>>str;
		str1 = 0, str2 = 0;
		ll num1 = 0, num2 = 0;
		ll m1 = 1, m2 = 1;
		for(int i=str.size()-1; i>=0; i--){
			num1 = (num1 + p[str[i]-'a'] * m1) % DIV;
			m1 = (m1 * P1) % DIV;
			arr[str.size()-i] = num1;
		}
		printf("%d\n", calc());
	}
	return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:89:16: warning: unused variable 'num2' [-Wunused-variable]
   ll num1 = 0, num2 = 0;
                ^~~~
palindromic.cpp:90:14: warning: unused variable 'm2' [-Wunused-variable]
   ll m1 = 1, m2 = 1;
              ^~

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40