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
#include <cstdio>
#include <cstdlib>

#include <vector>

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

#include <algorithm>

typedef long long ll;

int nodeID;
int nodeCount;

ll length;

char getProxyLetter(int i)
{
    if (i == 0) {
        return '^';
    }
    if (i == length - 1) {
        return '$';
    }
    if (i & 1) {
        return GetLetter(i / 2);
    }
    return '.';
}

void work()
{
    std::vector<int> radii;
    radii.reserve(length);

    int i = 1;
    int j = 0;

    radii.push_back(0);

    while (i < length - 1) {
        while (getProxyLetter(i - j - 1) == getProxyLetter(i + j + 1)) {
            j++;
        }
        radii.push_back(j);

        int k = 1;
        while (radii[i - k] != radii[i] - k && k <= j) {
            radii.push_back(std::min(radii[i - k], radii[i] - k));
            k++;
        }

        j = std::max(j - k, 0);
        i += k;
    }

    radii.push_back(0);

    ll sum = 0;
    for (int i = 1; i < length; i += 2) {
        int f1 = ((radii[i]) / 2) + 1;
        int f2 = (radii[i + 1] + 1) / 2;
        sum += (ll)(f1 + f2);
        // printf("%c %d: %d\n", getProxyLetter(i), i, f1);
        // printf("%c %d: %d\n", getProxyLetter(i + 1), i + 2, f2);
    }

    printf("%lld\n", sum);
}

int main()
{
    nodeID = MyNodeId();
    // nodeCount = NumberOfNodes();

    // Unfortunately, no parallelism... :(
    if (nodeID > 0) {
        return 0;
    }

    length = GetLength();
    length = 2 * length + 1;

    work();

    return 0;
}