1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include "message.h"
#include "palindromy.h"

using namespace std;

int n, kompy, ID, poczatek, koniec, pseudopoczatek, pseudokoniec, A, B;
long long result, wynik;
char znak[60000000];
string wyraz;

vector <int> v1;
vector <int> v2;

vector <int> Manacher1 (string s)
{
  	string x("$");
	x += s;
	x += '#';
 	vector <int> R;
 	R.push_back(0);
 	int i = 1, j = 0;
 	while (i <= x.size() - 1)
 	{
 		while (x[i - j] == x[i + j + 1]) j++;
   		R.push_back(j);
    	int k = 1;
    	while (R[i - k] != R[i] - k && k <= j)
    	{
    		R.push_back(min(R[i - k], R[i] - k));
     		k++;
    	}
    	j = max(j - k, 0);
		i += k;
  	}
  	return R;
}

vector <int> Manacher2 (string s)
{
    string x("$");
	x += s;
	x += '#';
    vector <int> R;
    R.push_back(0);
    int i = 1, j = 0;
    while (i <= x.size() - 1)
 	{
  		while (x[i - j - 1] == x[i + j + 1]) j++;
    	R.push_back(j);
    	int k = 1;
    	while (R[i - k] != R[i] - k && k <= j)
    	{
      		R.push_back(min(R[i - k], R[i] - k));
			k++;
    	}
    	j = max(j - k, 0);
		i += k;
  	}
  	return R;
}

int main ()
{
	n = GetLength();
	kompy = NumberOfNodes();
	ID = MyNodeId();
	if (n <= 10000000)
	{
		if (ID == 0)
		{
			for (int i = 0; i < n; ++i) znak[i] = GetLetter(i);
			wyraz = znak;
			v1 = Manacher1(wyraz);
			v2 = Manacher2(wyraz);
			for (int i = 1; i < n; ++i) result += (long long)(v1[i]);
			for (int i = 1; i <= n; ++i) result += (long long)(v2[i] + 1);
			printf("%lld\n", result);
		}
		return 0;
	}
	poczatek = (n / kompy) * ID;
	koniec = (n / kompy) * (ID + 1);
	if (ID == kompy - 1) koniec = n;
	if (ID == 0) pseudopoczatek = 0;
	else pseudopoczatek = ((n / kompy) * (2 * ID - 1)) / 2;
	if (ID == kompy - 1) pseudokoniec = n;
	else pseudokoniec = ((n / kompy) * (2 * ID + 3)) / 2;
	for (int i = pseudopoczatek; i < pseudokoniec; ++i) znak[i - pseudopoczatek] = GetLetter(i);
	wyraz = znak;
	v1 = Manacher1(wyraz);
	v2 = Manacher2(wyraz);
	for (int i = poczatek - pseudopoczatek + 1; i <= koniec - pseudopoczatek; ++i)
	{
		result += (long long)(v1[i]);
		A = i + pseudopoczatek - v1[i] - 1;
		B = i + pseudopoczatek + v1[i];
		while ((A >= 0) && (B < n) && (GetLetter(A) == GetLetter(B)))
		{
			result++;
			A--;
			B++;
		}
		result += (long long)(v2[i] + 1);
		A = i + pseudopoczatek - v2[i] - 2;
		B = i + pseudopoczatek + v2[i];
		while ((A >= 0) && (B < n) && (GetLetter(A) == GetLetter(B)))
		{
			result++;
			A--;
			B++;
		}
	}
	PutLL(0, result);
	Send(0);
	if (ID == 0)
	{
		wynik = 0;
		for (int i = 0; i < kompy; ++i)
		{
			Receive(i);
			result = GetLL(i);
			wynik += result;
		}
		printf("%lld\n", wynik);
	}
	return 0;
}