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

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

using namespace std;

int instances_nr = 100;
int max_k =   1000000;
int max_n = 100000000;
int k_per_instance = ceil(max_k/instances_nr);
unsigned long long *partials_sum = new unsigned long long[k_per_instance];
unsigned long long *tmp_sum = new unsigned long long[k_per_instance];

int main() {
    instances_nr = NumberOfNodes();
    int node_id = MyNodeId();
//    if(node_id != 0) return 0;

//      std::mt19937 generator{std::random_device{}()};
//      std::uniform_int_distribution<int> distribution(1,max_k);
//      auto dice = std::bind ( distribution, generator );
//      ofstream myfile;
//      myfile.open ("example.txt");
//      myfile << max_n << "\n";
//      for(int i = 0; i < max_n; i++) {
//
//          int wisdom = dice();
//          myfile << wisdom << " ";
//      }
//
//      myfile.close();

     for(int i = 0; i < k_per_instance; i++) {
        partials_sum[i] = 0;
        tmp_sum[i] = 0;
     }

//    int n = GetN();
//    cout << n << "\n";
//    int sum = 0;
//    for(int k = 0; k <= 100; ++k) {
//        int cur = 1 + k * instances_nr + node_id;
//        int tmp_sum = 0;
//        int par_sum = 0;
//        for (int i = n-1; i >= 0; --i) {
//            int hight = GetElement(i);
//            if (hight < cur) {
//                ++tmp_sum;
//            } else if (hight == cur) {
//                par_sum += tmp_sum;
//            }
//        }
//        sum += par_sum;
//    }

    int n = GetN();
//    cout << n << "\n";
    int sum = 0;
    for (int i = n-1; i >= 0; --i) {
        int hight = GetElement(i);
        int idx = ceil(hight / instances_nr);
        int rest = hight % instances_nr;
        if (rest > node_id) {
            idx += 1;
        } else if (rest == node_id) {
            //recalculate
            int real_tmp_sum = 0;
            for (int k = 0; k <= idx; ++k) { //idx
                real_tmp_sum += tmp_sum[k];
//                cout << "a " << hight << ":" << tmp_sum[k] << "\n";
            }
            partials_sum[idx] = real_tmp_sum;
        }
//        cout << hight << ":" << idx << "\n";
        tmp_sum[idx] += 1;
    }
    for (int i = 0; i < k_per_instance; ++i) {
//        if (partials_sum[i] > 0) {
//            int k = instances_nr*i + node_id;
//            cout << "b " << k << ":" << partials_sum[i] << endl;
//        }
        sum += partials_sum[i];
    }
    if (node_id > 0) {
        PutLL(0, sum);
        Send(0);
        return 0;
    }
    for(int i = 0; i < instances_nr-1; ++i) {
        int message = Receive(-1);
        sum += GetLL(message);
    }
    cout << sum << "\n";
}