#include "teatr.h" #include "message.h" #include <iostream> #include <cstdint> #include <cmath> #define PRINTF(ARG) std::cout << #ARG; #define PRINT(ARG) std::cout << #ARG << " = " << ARG << std::endl; typedef int32_t int32; typedef int64_t int64; const int32 MAX_HEIGHT = 1000000; const int32 MAX_RANGE = 10000; int32 tab[MAX_RANGE]; int64 conflicts; int main(){ int32 N = GetN(); int32 ID = MyNodeId(); int32 nodesCount = NumberOfNodes(); struct { int32 top,bottom,range; bool belong(int32 v) const{ return (v >= bottom && v < top); } void print() {std::cout << "<" << bottom << "," << top << ")" << "-" << range << "; "; } } bounds; int32 leap = std::floor((double)MAX_HEIGHT/(double)nodesCount); bounds.bottom = ID * leap; bounds.top = (ID == (nodesCount-1) ? MAX_HEIGHT : (ID+1)*leap); bounds.range = bounds.top - bounds.bottom; for(int32 k=0; k<N; k++){ int32 height = GetElement(k); int32 localHeight = height - bounds.bottom; if(localHeight > bounds.range) localHeight = bounds.range; for(int32 h=0; h<localHeight; h++){ tab[h]++; } if(bounds.belong(height)){ conflicts += tab[localHeight]; } } if(ID > 0){ PutLL(0, conflicts); Send(0); }else{ for(int32 inst = 1; inst < nodesCount; ++inst){ Receive(inst); conflicts += GetLL(inst); } std::cout << conflicts << std::endl; } }
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 | #include "teatr.h" #include "message.h" #include <iostream> #include <cstdint> #include <cmath> #define PRINTF(ARG) std::cout << #ARG; #define PRINT(ARG) std::cout << #ARG << " = " << ARG << std::endl; typedef int32_t int32; typedef int64_t int64; const int32 MAX_HEIGHT = 1000000; const int32 MAX_RANGE = 10000; int32 tab[MAX_RANGE]; int64 conflicts; int main(){ int32 N = GetN(); int32 ID = MyNodeId(); int32 nodesCount = NumberOfNodes(); struct { int32 top,bottom,range; bool belong(int32 v) const{ return (v >= bottom && v < top); } void print() {std::cout << "<" << bottom << "," << top << ")" << "-" << range << "; "; } } bounds; int32 leap = std::floor((double)MAX_HEIGHT/(double)nodesCount); bounds.bottom = ID * leap; bounds.top = (ID == (nodesCount-1) ? MAX_HEIGHT : (ID+1)*leap); bounds.range = bounds.top - bounds.bottom; for(int32 k=0; k<N; k++){ int32 height = GetElement(k); int32 localHeight = height - bounds.bottom; if(localHeight > bounds.range) localHeight = bounds.range; for(int32 h=0; h<localHeight; h++){ tab[h]++; } if(bounds.belong(height)){ conflicts += tab[localHeight]; } } if(ID > 0){ PutLL(0, conflicts); Send(0); }else{ for(int32 inst = 1; inst < nodesCount; ++inst){ Receive(inst); conflicts += GetLL(inst); } std::cout << conflicts << std::endl; } } |