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
#include "kollib.h"
#include "message.h"
#include <stdio.h>
#include <stdlib.h>

int slave();
int master();

int *cache;
int DIV;

void cacheMem() {
        int from,to,a,pa,c,i,n,t;
        DIV = NumberOfStudents() / NumberOfNodes();
        if (NumberOfStudents() % NumberOfNodes()) DIV++;
        from = MyNodeId() * DIV;
        to = (MyNodeId()+1) * DIV;

        if (to > NumberOfStudents()) to = NumberOfStudents();
        cache = malloc(DIV * sizeof(*cache));
        c = a = pa = 1;
        n = NumberOfStudents();
        for (i=0; i<n; ++i) {
                if ((a-1)>=from && (a-1)<to) {
                        cache[(a-1)-from] = i;
                }
                t = a;
                a = FirstNeighbor(a);
                if (a == pa) a = SecondNeighbor(t);
                pa = t;
        }

}

int getFromCache(int q) {
        int n,i;
        q--;
        n = q / DIV;
        i = q % DIV;
        if (n == 0 && MyNodeId() == 0) {
                return cache[i];
        }
        PutInt(n,i);
        Send(n);
        Receive(n);
        return GetInt(n);
}

int master() {
        int i,n,nodes,a,b,r;
        n = NumberOfQueries();
        nodes = NumberOfNodes();

        for (i=1; i<=n; ++i) {
                a = getFromCache(QueryFrom(i));
                b = getFromCache(QueryTo(i));
                r = a > b ? a-b : b - a;
                if (r > NumberOfStudents()-r)
                        r = NumberOfStudents()-r;
                printf("%d\n", r);
        }
        for (i=0; i<nodes; ++i) {
                PutInt(i,-1);
                Send(i);
        }
        return 0;
}

int slave() {
        int q;
        for (;;) {
                Receive(0);
                q = GetInt(0);
                if (q<0) return 0;
                PutInt(0, cache[q]);
                Send(0);
        }
        return 0;
}


int main() {
        cacheMem();
        if (MyNodeId() == 0) {
                master();
        } else {
                slave();
        }
        free(cache);
        return 0;
}