Submission #199681

#	Time	Username	Problem	Language	Result	Execution time	Memory
199681		rKrPaN	Palindromic Partitions (CEOI17_palindromic)	C++98	100 / 100	568 ms	19148 KiB

palindromic

#include <iostream>
#include <string>

using namespace std;

long long H[1000100];
long long pot[1000100];

long long h(int l, int d){
	l++; d++;
	return H[d] - H[l-1] * pot[d-l+1];
}

int main(){

	int t;
	cin >> t;
	for (int ij = 0; ij < t; ij++){
		
		string s;
		cin >> s;
		
		int n = s.size();
		
		H[1] = s[0]-'a';
		pot[1] = 37;
		int p = 1;
		for (int i = 2; i <= n; i++){
			H[i] = 37*H[i-1] + s[i-1]-'a';
			pot[i] = pot[i-1] * 37;
		}
		int sol = 1;
		
		int d = 1, o = 0;
		for (int i = 0; i < n/2; i++){
			
			long long hl = h(o, o + d-1);
			long long hd = h(n-o-d, n-o-1);
		/*
			cout << d << " " << o << "\n";
			cout << sol << "\n";
			cout << hl << " " << hd << "\n";
		*/	
			if (hl == hd){
				o += d;
				d = 0;
				sol+= 2;
			}
			
			d++;
		}
		if (n%2 == 0 && d == 1)sol--;
		cout << sol << "\n";
		
	}
	return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:27:7: warning: unused variable 'p' [-Wunused-variable]
   int p = 1;
       ^

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