Cod sursa(job #1499417)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 10 octombrie 2015 16:36:54
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

template <typename F>
void pscpld(const int n, F f, vector<int>& v){
	int poz_max = -1, centru_poz_max = 0;
	for(int i = 0; i < n; ++i){
		if(i > poz_max){
			int j = 1;
			for( ; 0 <= i-j && i+j < n && f(i-j, i+j); ++j);
			--j;
			v[i] = j;
			if(i+j >= poz_max){
				poz_max = i+j;
				centru_poz_max = i; } }
		else{
			const int val_omolog = v[2*centru_poz_max - i];
			if(i+val_omolog < poz_max){
				v[i] = val_omolog; }
			else{
				int j = poz_max - i;
				for( ; 0 <= i-j && i+j < n && f(i-j, i+j); ++j);
				--j;
				v[i] = j;
				if(i+j >= poz_max){
					poz_max = i+j;
					centru_poz_max = i; } } } } }

int main(){
	ifstream f("pscpld.in");
	ofstream g("pscpld.out");
	string str;
	f >> str;
	vector<int> v(2*str.size()+1);

	pscpld(2*str.size()+1,
		[&str](const int a, const int b){
			return (a%2 == 0 && b%2 == 0) ||
				(a%2 == 1 && a%2 == 1 && str[a/2] == str[b/2]); }, v);
	long long rez = 0;
	for(const auto x : v){
		rez += (x+1)/2; }
	g << rez;
	return 0; }