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
#include "message.h"
#include "teatr.h"

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

LL Sort(vector<int>& t, int a, int b, vector<int>& p) {
  if (b-a < 2) return 0;
  int c = (a+b)/2;
  LL result = Sort(t, a, c, p) + Sort(t, c, b, p);

  int i = a, j = c;
  for (int k=a; k<b; ++k) {
    if (j == b){
      p[k] = t[i++];
      continue;
    }
    if (i != c && t[i] <= t[j]) {
      p[k] = t[i++];
      continue;
    }
    p[k] = t[j++];
    result += c-i;
  }
  for (int k=a; k<b; ++k) {
    t[k] = p[k];
  }
  return result;
}

int main() {
  int n = GetN();
  int nodes = NumberOfNodes();

  if (nodes != 100) {
    printf("Testy powinny byc uruchamiane na 100 instancjach.\n");
    exit(1);
  }

  int node_id = MyNodeId();

  int a = -1, b = -2, d = 13;
  int rest = node_id;
  for (int i=0; i<d; ++i) {
    for (int j=i; j<d; ++j) {
      if (rest == 0) {
        a = i;
        b = j;
      }
      --rest;
    }
  }
  int ai = n*a/d;
  int aj = n*(a+1)/d;

  int bi = n*b/d;
  int bj = n*(b+1)/d;

  long long result = 0;

  if (a == b) {
    vector<int> aa(aj-ai), bb(aj-ai);
    for (int i=ai; i<aj; ++i) {
      aa[i-ai] = GetElement(i);
    }
    result = Sort(aa, 0, aa.size(), bb);
  } else if (a < b) {
    vector<int> aa(aj-ai);
    for (int i=ai; i<aj; ++i) {
      aa[i-ai] = GetElement(i);
    }
    sort(aa.begin(), aa.end());

    for (int i=bi; i<bj; ++i) {
      int v = GetElement(i);
      auto it = upper_bound(aa.begin(), aa.end(), v);
      result += distance(it, aa.end());
    }
  }
  
//  printf("Licze %d %d: (%d %d) x (%d %d) = %lld\n", a, b, ai, aj, bi, bj, result);

  if (node_id != 0) {
    PutLL(0, result);
    Send(0);
  } else {
    for (int i=1; i<nodes; ++i) {
      Receive(i);
      result += GetLL(i);
    }
    printf("%lld\n", result);
  }

  return 0;
}