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
// Jedna instancja wypisuje maksymalny wzrost.

#include "message.h"
#include "teatr.h"
#include "bits/stdc++.h"

const int max_num = 6;
int tab[max_num + 3], a;
// TODO: partial sum structure (sum bigger than)
// Q: czy tylko kolejnosc wewnatrz bufora jest zapewniona, czy tez dwa wywolania
// PutInt(), Send(), PutInt(), Send() przyjda w tej samej kolejnosci?
// Czy nalezy zalozyc, ze Send trwa duzo dluzej niz PutInt, czy oba te czasy sa
// pomijalne (przy zalozeniu, ze zostanie wyslane < 1000 wiadomosci o lacznej
// wielkosci < 8KB?)
long long res, r1;
int my_node_id;
using namespace std;
const int instance_num = 100;

int readfrom(int x){
  return GetInt(Receive(x));
}

void sendNext(int x) {
  for(int i = my_node_id + 1; i < instance_num; i++) {
    PutInt(i, x);
  }
}

int total_x_before(){
  int num = 0;
  for(int i = 0; i < my_node_id; i++) {
    Receive(i);
    num += readfrom(i);
  }
  return num;
}

void readall() {
  for(int i = 0; i < my_node_id; i++) {
    Receive(i);
    for(int j = 1; j<max_num; j++) {
      res += (long long)(tab[j]) * (long long)(GetInt(i));
    }
  }
}

int main() {
  my_node_id = MyNodeId();
  int n = GetN();
//  cout << n << "\n";
  int my_range_start = (n / instance_num) * my_node_id;
  int my_range_end = (n / instance_num) * (my_node_id + 1);
  if (my_node_id == instance_num - 1){
    my_range_end = n;
  }
//  cout << my_node_id << " start end" << my_range_start << " " << my_range_end << "\n";
  for(int i=my_range_start; i<my_range_end;i++){
//    cout << "my node" << my_node_id << " " << res << "\n";
    a = GetElement(i);
//    cout << a << "a\n";
    for(int j=a+1; j <=max_num; j++){
      res += tab[j];
    }
    tab[a]++;
 //   cout << "my node" << my_node_id << " " << res << "\n";
  }
  for(int i = 2; i <= max_num; i++) {
    sendNext(tab[i]);
  }
  for (int i = my_node_id + 1; i < instance_num; i++) {
    Send(i);  // sending max_num - 1 numbers each
  }
  for(int i=1; i < max_num; i++)
    tab[i+1] += tab[i];
  readall();
  if (my_node_id == 0){
    for(int i = 1; i < instance_num; i++){
      r1 = GetLL(Receive(i));
//      cout << "got " << r1 << "from " << i << "\n";
      res += r1;
    }
    cout << res << "\n";
  } else {
    PutLL(0, res);
    Send(0);
  }
}