#include <cstdio> #include <algorithm> #include "message.h" #include "poszukiwania.h" using namespace std; typedef long long LL; int match(int mess_offset, int sig_offset, LL limit) { // number of comparison matches until end or mismatch for(int i = 0; i < limit; ++i) { if(SignalAt(i + sig_offset + 1) != SeqAt(i + mess_offset + 1)) { return i; } } return limit; } int main() { LL siglen = SignalLength(); LL messagelen = SeqLength(); int positions = messagelen - siglen + 1; int nodes = NumberOfNodes(); int node_id = MyNodeId(); if(positions >= nodes || (siglen / nodes) == 0) { // many shifts, each instance calculates her shifts // or signals are too short to be split among instances like we do in second case LL results = 0; for(int pos = node_id; pos < positions; pos += nodes) { if(match(pos, 0, siglen) == siglen) { ++results; } } PutLL(0, results); Send(0); if(node_id == 0) { LL final_results = 0; for(int inst = 0; inst < nodes; ++inst) { Receive(inst); final_results += GetLL(inst); } printf("%lld\n", final_results); } } else { // few shifts, preferably long signals, instances work together on same shifts int work_per_inst = siglen / nodes; for(int pos = 0; pos < positions; ++pos) { int start = node_id * work_per_inst; // instance offset LL matched = match(start + pos, start, work_per_inst); if(node_id == nodes - 1) { // last one works harder int left = siglen - nodes * work_per_inst; if(matched == work_per_inst && left > 0) { // dont overdo matched += match(pos + siglen - left, 0, left); } } PutLL(0, matched); } Send(0); if(node_id == 0) { LL final_results = 0; for(int inst = 0; inst < nodes; ++inst) { Receive(inst); } for(int pos = 0; pos < positions; ++pos) { LL parts = 0; for(int inst = 0; inst < nodes; ++inst) { parts += GetLL(inst); } if(parts == siglen) { ++final_results; } } printf("%lld\n", final_results); } } return 0; }
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 | #include <cstdio> #include <algorithm> #include "message.h" #include "poszukiwania.h" using namespace std; typedef long long LL; int match(int mess_offset, int sig_offset, LL limit) { // number of comparison matches until end or mismatch for(int i = 0; i < limit; ++i) { if(SignalAt(i + sig_offset + 1) != SeqAt(i + mess_offset + 1)) { return i; } } return limit; } int main() { LL siglen = SignalLength(); LL messagelen = SeqLength(); int positions = messagelen - siglen + 1; int nodes = NumberOfNodes(); int node_id = MyNodeId(); if(positions >= nodes || (siglen / nodes) == 0) { // many shifts, each instance calculates her shifts // or signals are too short to be split among instances like we do in second case LL results = 0; for(int pos = node_id; pos < positions; pos += nodes) { if(match(pos, 0, siglen) == siglen) { ++results; } } PutLL(0, results); Send(0); if(node_id == 0) { LL final_results = 0; for(int inst = 0; inst < nodes; ++inst) { Receive(inst); final_results += GetLL(inst); } printf("%lld\n", final_results); } } else { // few shifts, preferably long signals, instances work together on same shifts int work_per_inst = siglen / nodes; for(int pos = 0; pos < positions; ++pos) { int start = node_id * work_per_inst; // instance offset LL matched = match(start + pos, start, work_per_inst); if(node_id == nodes - 1) { // last one works harder int left = siglen - nodes * work_per_inst; if(matched == work_per_inst && left > 0) { // dont overdo matched += match(pos + siglen - left, 0, left); } } PutLL(0, matched); } Send(0); if(node_id == 0) { LL final_results = 0; for(int inst = 0; inst < nodes; ++inst) { Receive(inst); } for(int pos = 0; pos < positions; ++pos) { LL parts = 0; for(int inst = 0; inst < nodes; ++inst) { parts += GetLL(inst); } if(parts == siglen) { ++final_results; } } printf("%lld\n", final_results); } } return 0; } |