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
#include "poszukiwania.h"
#include "message.h"

#include <cstdio>
#include <stack>
#include <set>

std::stack<int> refused;	// zbiór niedopasowanych
std::set<int>	missed;		// wspólny zbiór niedopasowanych w głównym wątku grupy

int main() {
	const long long S = SignalLength();		// wzorzec
	const long long M = SeqLength();		// wejście
	
	const int nodeId = MyNodeId();
	const int nodesNum = NumberOfNodes();
  
	const long long maxMatches = M - S + 1; // maksymalna liczba dopasowań
	const long long groupsNum = maxMatches > nodesNum ? nodesNum : maxMatches;

	// identyfikator grupy
	const int groupId = nodeId % groupsNum;
	// liczba maszyn w grupie
	const int groupSize = (nodesNum - groupId + groupsNum - 1) / groupsNum;

	// liczba dopasowań w grupie
	for (int i = groupId; i < maxMatches; i += groupsNum) {
		// i - indeks porównywania w wejściu
		// j - indeks we wzorcu
		int j = nodeId / groupsNum;
		while (j < S && SeqAt(i + j + 1) == SignalAt(j + 1))
			j += groupSize;

		// czy zgodne z wzorcem
		bool matched = j >= S;
		if (!matched) {
			if (nodeId != groupId) {
				// wysyłamy do głównego wątku w grupie informację o braku
				// dopasowania od i
				refused.push(i);
			} else {
				missed.insert(i);
			}
		}
	}

	if (nodeId != groupId) {
		//printf("b %d %d", nodeId, refused.size()); fflush(stdout);
		PutLL(groupId, refused.size());
		while(!refused.empty()) {
			PutInt(groupId, refused.top());
			refused.pop();
		}
		Send(groupId);
	} else {
		// główny wątek w grupie
		//printf("a %d", nodeId); fflush(stdout);
		for (int j = groupId + groupsNum; j < nodesNum; j += groupsNum) {
			Receive(j);
			int size = GetLL(j);
			//printf("j %d %d", j, size); fflush(stdout);
			while (size--)
				missed.insert(GetInt(j));
		}
		// wysyłamy do głównego wątku informacje o braku dopasowań
		if (nodeId > 0) { 
			PutLL(0, missed.size());
			Send(0);
		}
	}

	long long unmatched = missed.size();

	if (nodeId == 0) {
		// odbieramy liczbę od głównych wątków
		for (int i = 1; i < groupsNum; ++i) {
			int nodeNr = Receive(-1);
			unmatched += GetLL(nodeNr);
		}
		printf("%lld", maxMatches - unmatched);
	}

  	return 0;
}