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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
//  budowanie za pomocą polecenia:
/// rpa build --source=pal2.cpp
//
//  uruchamianie
/// rpa run --executable=./pal2 --nodes=100 --output=all
//
//  komplet:
/// rpa build --source=pal2.cpp && rpa run --executable=./pal2 --nodes=100 --output=all < pal0a.in

#include<iostream>

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

using namespace std;

//#define DEBUG
//#define ASSERT

#ifdef DEBUG
#define ifdebug if(true)
#else
#define ifdebug if(false)
#endif

#ifdef ASSERT
#define ifassert if(true)
#else
#define ifassert if(false)
#endif


#define BITS	3
#define BLOCK	(1<<BITS)
#define BFIX(x) ((x)&~BLOCK)
#define TOB(x)	((x)>>BITS)

int *R=NULL;

/// Pomocnicza funkcja, która sprawdza rozmiar maksymalnego palindromu z danej pozycji
int checkPalindrom(const int i, const int j, const int n) {
	int rp=0;

	while( (i-rp-1>=0) && ((i+j+rp)<n) && GetLetter(i-rp-1)==GetLetter(i+j+rp)) ++rp;
	return rp;
}

/// Funkcja zwracająca ilość palindromów o długości >1 w ciągu bazując na algorytmie Mahacher-a
int64_t searchPalindromesSimple(const int j, const int n) {
	int k,rp, i;
	if(R==NULL) R=new int[n+1];

	R[0]=rp=0;
	i=0;

	while(i<n) {
		while( (i-rp-1>=0) && ((i+j+rp)<n) && GetLetter(i-rp-1)==GetLetter(i+j+rp)) ++rp;
		R[i+1]=rp;
		k=1;
		while( (R[i-k+1]!=rp-k) && (k<rp)) {
			R[i+k+1]=min(R[i-k+1], rp-k);
			++k;
		}
		rp=max(rp-k, 0);
		i+=k;
	}
	int64_t sum=0;
	for(int i=1;i<=n;++i) sum+=R[i];

	//delete[] R;	nie usuwamy, bo algorytm będzie uruchamiany dwa razy

	return sum;
}

/// Funkcja zwracająca ilość palindromów w ciągu bazując na algorytmie Manacher-a
int64_t searchPalindromes(const int offset, const int j, const int n) {
	int bn=(n+BLOCK-1)/BLOCK+1;	// ilość bloków
	int k,rp, i;
	if(R==NULL) R=new int[bn];
	//ifdebug cerr<<"Iteration start: offset="<<offset<<", j="<<j<<", n="<<n<<endl;

	R[0]=rp=0;
	i=offset;

	while(i<n) {
		while( (i-rp-1>=0) && ((i+j+rp)<n) && GetLetter(i-rp-1)==GetLetter(i+j+rp)) ++rp;
		R[TOB(i)+1]=rp;	// pozycja bloku
		k = BLOCK;			// pierwsza wielokrotność bloku

		while( (k<rp) && ((R[ TOB(i)-TOB(k)+1 ]) != rp-k) ) {
			R[ TOB(i)+TOB(k)+1 ] = min(R[ TOB(i)-TOB(k)+1 ], rp-k);
			k+=BLOCK;
		}
		rp=max(rp-k, 0);

		i+=k;
	}
	int64_t res=0;
	for(int i=1;i<bn;++i) {
		res+=R[i];
		/*ifassert {
			int pos=(((i-1)*BLOCK)+offset);
			int simple=checkPalindrom(pos, j, n);

			if(simple!=R[i]) {
				cerr<<"Invalid value at position: "<< pos<<" ("<<i<<") m="<<R[i]<<" simple="<<simple<<endl;
				throw "Error";
			}
		}*/
	}

	//delete []R;
	//ifdebug cerr<<"Iteration end: offset="<<offset<<", j="<<j<<", n="<<n<<" result: "<<res<<endl;

	return res;
}

int main(int argc, char** argv) {
    const int myId=MyNodeId();  /// id wezła
    const int nodes=NumberOfNodes();    /// ilość węzłów

    const int len=GetLength();  // długość ciągu

    if(len<10000000)
    //if(len<100)	// na potrzeby testu wielozadaniowości
	{   // jeżeli ciąg jest krótki, to badamy go na jednym węźle, bo działą to wczasie liniowym
        if(nodes==1) {
			if(myId!=0) return 0;
			// wynik to suma dla parzystych, nieparzystych ciągów oraz ilości liter w ciągu, bo każda z nich jest palindromem według definicji z treści zadania
			int64_t sum=searchPalindromesSimple(0,len)+searchPalindromesSimple(1,len)+len;

			cout<<sum<<endl;
        } else if(nodes>1) {	// jeżeli przynajmniej dwa węzły, to liczmy na dwóch
        	if(myId==1) {
				int64_t sum=searchPalindromesSimple(1,len);
				PutLL(0,sum);
				Send(0);
        	} else if(myId==0) {
        		int64_t sum=searchPalindromesSimple(0,len)+len;
        		Receive(1);
        		sum+=GetLL(1);

        		cout<<sum<<endl;
        	}
        }

        return 0;
    }

    // dla pozostałych (dłuższych) ciągów, ponieważ nie ma wystarczająco pamięci (512 MB), to liczyby blokami i dzielimy zadanie na różne komputery

	int task=0;
	int64_t sum=0;
	for(int j=0;j<2;++j) {
		for(int i=0;i<BLOCK;++i) {
			if(task%nodes==myId) {	// wykonujemy zadanie na kolejnych węzłach
				ifdebug cerr<<"["<<myId<<"] Processing task: j="<<i<<", i="<<i<<endl;
				sum+=searchPalindromes(i, j, len);
			}
			++task;
		}
	}


	if(myId>0) {	// i wysyłamy ze wszystkich wezłów do pierwszego
		if(myId<task) {	// tylko węzły, które coś robiły wysyłają wyniki; jeżeli wezłów jest więcej niż zadań, to nie wykonują one zadań
			ifdebug cerr<<"["<<myId<<"] Sending part sum: "<<sum<<endl;
			PutLL(0, sum);
			Send(0);
		}
	} else {	// zbieramy wyniki ze wszystkich wezłów
		int workers=min(task, nodes);	// tyle wezłów było używane;
		ifdebug cerr<<"["<<myId<<"] Receiving sums from "<<workers<<" nodes"<<endl;
		for(int i=1;i<workers;++i) {
			Receive(i);
			sum+=GetLL(i);
		}
		sum+=len;		// dodajemy palindromy pojedyńcze
		cout<<sum<<endl;	// i wyświetlamy wynik
	}

    return 0;
}