I’ve got MLE. So I couldn’t advance the round 2. If there was a practice round or I joined the last year’s one, I could…

## solution

Compute the maximum of the difference of items.

Distribute the ranges into the nodes, calculate max and min in each node, and solve in the master node. $O(N / P)$ where $P$ is the number of nodes.

## memo

### limits

• The memory limit is often very small.
• The Send/Receive limit is a bit large.

### how to test

-Wall,-D_GLIBCXX_DEBUG is important.

$../dcj-testing-tool/dcj.sh build --source=a.cpp --extra_flags=-Wall,-D_GLIBCXX_DEBUG$ ../dcj-testing-tool/dcj.sh run --executable=./a --nodes=100 --output=all


$ls *.h oops.1.h oops.2.h oops.3.h oops.h$ cat oops.h
#include "oops.1.h"


### distribute items into nodes

int l = n *(ll) my_id / nodes;
int r = n *(ll) (my_id + 1) / nodes;
repeat_from (i,l,r) { ... }


or

for (int i = my_id; i < n; i += nodes) { ... }


### nodes whose range is empty

if (n <= nodes) {
nodes = n;
if (nodes <= my_id) return 0;
}


## implementation

If you use vector<int> ans sort( ... ), it causes RE (I think this RE is MLE with std::bad_alloc).

#include <message.h>
#include "oops.h"
#define MASTER_NODE 0

#include <iostream>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <class T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }
template <class T> bool setmin(T & l, T const & r) { if (not (r < l)) return false; l = r; return true; }

int main() {
ll nodes = NumberOfNodes();
ll my_id = MyNodeId();
ll n = GetN();

ll l = n * my_id / nodes;
ll r = n * (my_id + 1) / nodes;
ll max_x = GetNumber(0);
ll min_x = GetNumber(0);
repeat_from (i,l,r) {
ll x = GetNumber(i);
setmax(max_x, x);
setmin(min_x, x);
}
PutLL(MASTER_NODE, max_x);
PutLL(MASTER_NODE, min_x);
Send(MASTER_NODE);

if (my_id == MASTER_NODE) {
repeat (node,nodes) {