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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#include "message.h"
#include "palindromy.h"

namespace {

struct String {
  int n;

  String():
    n(2 * GetLength() + 1)
  {
  }

  int size() const
  {
    return n;
  }

  char operator[](int i) const
  {
    if ((i & 1) == 0) return '.';
    return GetLetter(i >> 1);
  }
};

}

int main()
{
  int k = NumberOfNodes();
  int id = MyNodeId();
  if (id >= k) return 0;

  String s;

  int n = s.size();

  int left = (id + 0LL) * n / k;
  int right = (id + 1LL) * n / k;

  vector<int> p(right - left);
  int best_c = 0, best_r = 0;
  for (int i = left; i < right; i++) {
    int cur;
    if (i > best_r || best_c - (i - best_c) < left) {
      cur = 0;
    } else {
      cur = min(p[best_c - (i - best_c) - left], best_r - i);
    }
    auto l = i - cur - 1;
    auto r = i + cur + 1;
    while (l >= 0 && r < n && s[l] == s[r]) {
      --l;
      ++r;
    }
    cur = i - l - 1;
    if (i + cur >= best_r) {
      best_c = i;
      best_r = i + cur;
    }
    p[i - left] = cur;
  }

  long long res = 0;
  for (int w: p) res += (w + 1) / 2;

  if (id > 0) {
    Receive(id - 1);
    res += GetLL(id - 1);
  }

  if (id < k - 1) {
    PutLL(id + 1, res);
    Send(id + 1);
  } else {
    cout << res << endl;
  }

  return 0;
}