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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include "teatr.h"
#include "message.h"
#include <vector>

using namespace std;
//Wezmy to rozwalmy przy pomocy merge sort

vector<int> rozloz(long long &wynik, vector<int> tab);

vector<int> skladaj(long long &wynik, vector<int> tab1, vector<int> tab2);
/*
int NumberOfNodes(){
    return 1;
}
int GetN(){
    int x;
    cin >> x;
    return x;
}
int MyNodeId(){
    return 1;
}
int GetElement(int i){
    cin >> i;
    return i;
}
void wypisz(vector<int> tab)
{
    int n=tab.size();
    for(int i=0; i<n; i++)
    {
        cout << tab[i] << " ";
    }
    cout << endl;
}*/
/* */


void wysylaj(vector<int> tab)
{
    int n=tab.size();
    for(int i=0; i<n; i++)
    {
        PutInt(0, tab[i]);
        Send(0);
    }
}/* */

int main()
{
    int n = GetN();
    int id = MyNodeId();
    long long wynik = 0;
    vector<int> tab;
    if(n<NumberOfNodes()){
    for(int i=0; i<n ; i++)
    {
        tab.push_back(GetElement(i));
    }
    }else if(id<n){
        tab.push_back(GetElement(id));
    }
    //wypisz(tab);
    tab = rozloz(wynik, tab);
    //wypisz(tab);

    if(id!=0)
    {
        //PutInt(0,wynik);
        //PutInt(0,tab.size());
        //wysylaj(tab);
    }else{
        cout << wynik << endl;
    }
    return 0;
}

vector<int> rozloz(long long &wynik, vector<int> tab){
    //wypisz(tab);
    vector<int> t1, t2;
    int n=tab.size();
    for(int i=0; i<n/2; i++){
        t1.push_back(tab[i]);
    }
    for(int i=n/2; i<n; i++){
        t2.push_back(tab[i]);
    }
    if(n>=4){
            //wypisz(t1);
        t1 = rozloz(wynik, t1);
    //wypisz(t1);
        t2 = rozloz(wynik, t2);
        return skladaj(wynik, t1, t2);
    }else if(n==3){
        t2 = rozloz(wynik, t2);
        return skladaj(wynik, t1, t2);
    }else{
        return skladaj(wynik, t1, t2);
    }
}

vector<int> skladaj(long long &wynik, vector<int> tab1, vector<int> tab2) //tab1 jest bardziej blizzsze widowni
{
    vector<int> t;
    int n = tab1.size(), m = tab2.size();
    int point1=0, point2=0;
    for(int i=0; i<n+m; i++){
            //wypisz(t);
        if(point1 == tab1.size()){
            t.push_back(tab2[point2++]);
        }else if(point2 == tab2.size()){
            t.push_back(tab1[point1++]);
        }else{
            if(tab1[point1]<=tab2[point2]){
                t.push_back(tab1[point1++]);
            }else{
                wynik+=n-point2;
                t.push_back(tab2[point2++]);
            }
        }
    }
    return t;
}