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

using namespace std;

int ile[6], pile[6];

long long inwersje;

const int tresh = 2e5;

int tab[tresh], pomoc[tresh];

void merge(int poczatek, int srodek, int koniec)
{
    int dl = koniec - poczatek + 1;
    for (int i = poczatek; i <= koniec; ++i) pomoc[i] = tab[i];

    int a = poczatek, b = srodek + 1, i = poczatek;

    while (a <= srodek && b <= koniec){
        if (pomoc[a] <= pomoc[b]) tab[i] = pomoc[a], ++a;
        else tab[i] = pomoc[b], ++b, inwersje+=(long long)(srodek-a+1);
        i++;
    }
    while (a <= srodek) tab[i] = pomoc[a], ++a, ++i;
    while (b <= koniec) tab[i] = pomoc[b], ++b, ++i;
}
void mergesort(int poczatek, int koniec)
{
    if (poczatek == koniec) return;
    int srodek = (poczatek + koniec)/2;
    mergesort(poczatek, srodek);
    mergesort(srodek + 1, koniec);
    merge(poczatek, srodek, koniec);
}

int main()
{
    int n = GetN();
    int mni = MyNodeId();

    if(n<tresh){
        if(mni!=0){
            return 0;
        }
        else{
            for(int i = 0; i<n; i++){
                tab[i] = GetElement(i);
            }
            mergesort(0, n-1);
            cout<<inwersje;
            return 0;

        }
    }

    for(int i = mni*n/99; i<min(n, (mni+1)*n/99); i++){
        int obecny = GetElement(i);
        ile[obecny]++;
        for(int j = obecny+1; j<6; j++){
            inwersje += (long long)ile[j];
        }
    }
    if(mni==0){
        PutLL(1, inwersje);
        for(int i = 2; i<6; i++){
            PutInt(1, ile[i]);
        }
        Send(1);
    }
    else{
        Receive(mni-1);
        inwersje+=GetLL(mni-1);
        for(int i = 2; i<6; i++){
            pile[i] = GetInt(mni-1);
        }
        for(int i = 1; i<6; i++){
            for(int j = i+1; j<6; j++){
                inwersje+=(long long)ile[i]*(long long)pile[j];
            }
        }
        if(mni<99){
            PutLL(mni+1, inwersje);
            for(int i = 2; i<6; i++){
                PutInt(mni+1, ile[i]+pile[i]);
            }
            Send(mni+1);
        }
        else{
            cout<<inwersje;
        }
    }

    return 0;
}