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 "message.h"
#include "teatr.h"
#include "bits/stdc++.h"

#define LEN 8

using namespace std;

int _max(int a, int b) {
    return (a<b) ? b : a;
}

int _min(int a, int b) {
    return (a<b) ? a : b;
}

int main() {
    int nodes, nodeid,  n, count, k, maxi, mini;
    long long res=0LL, r;
    int stats[LEN] = {0};
    
    nodes = NumberOfNodes();
    nodeid= MyNodeId();
    n = GetN();
    count = n/nodes;
    if(count*nodes < n)
        count++;
    maxi = 0;
    mini = 1000001;
    
    for(int i=nodeid*count; i<(nodeid+1)*count; i++) {
        if(i<n) {
            k = GetElement(i);
            if(maxi<k)
                maxi = k;
            if(k<mini)
                mini = k;
            for(int j=k+1; j<LEN && j<=maxi; j++) {
                res += stats[j];
            }
            stats[k]++;
        }
    }
//    cout << "res: " << res << endl;
    
    int sum=0;
    int x;
    if(nodeid) {
        Receive(nodeid-1);
        for(int i=1; i<LEN; i++) {
            sum += stats[i-1];
            x = GetInt(nodeid-1);
//            cout << "x: " << x << endl;
            res+= sum*x;
            PutInt((nodeid+1)%nodes, x+stats[i]);
        }
        PutInt((nodeid+1)%nodes, _max(maxi, GetInt(nodeid-1)));
        PutInt((nodeid+1)%nodes, _min(mini, GetInt(nodeid-1)));
        PutLL((nodeid+1)%nodes, res+GetLL(nodeid-1));
        Send((nodeid+1)%nodes);
        
    } else {
        for(int i=1; i<LEN; i++) {
            PutInt(1, stats[i]);
        }
        PutInt(1, maxi);
        PutInt(1, mini);
        PutLL(1, res);
        Send(1);

        Receive(nodes-1);
        for(int i=1; i<LEN; i++) {
            x = GetInt(nodes-1);
        }
        maxi = GetInt(nodes-1);
        mini = GetInt(nodes-1);
        res = GetLL(nodes-1);
        if(maxi < LEN) {
            cout << res << endl;
        } else { // giveup
            cout << -1LL << endl;
        }
    }
}