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
#include <cstdio>
#include <cstdlib>
#include "message.h"
#include "kollib.h"

#define N 25000001

int t[N];
int answer[201];

int main()
{
	int myid = MyNodeId();
	int nstudents = NumberOfStudents();

	int order = 1;
	if (nstudents < N) {
		int iterator = 1;
		t[iterator] = order;
		iterator = FirstNeighbor(iterator);
		while (order < nstudents) {
			order++;
			t[iterator] = order;
			if (t[FirstNeighbor(iterator)]) {
				iterator = SecondNeighbor(iterator);
			} else {
				iterator = FirstNeighbor(iterator);
			}
		}
		int nqueries = NumberOfQueries();
		for (int i = 1; i <= nqueries; i++) {
			int from = QueryFrom(i);
			int to = QueryTo(i);
			int minutes = t[to] - t[from];
			if (minutes < 0) minutes *= -1;
			if (nstudents - minutes < minutes) {
				minutes = nstudents - minutes;
			}
			if (!myid && nqueries) {
				printf("%d\n", minutes);
			}
		}
	} else {
		int nnodes = NumberOfNodes();
		int nqueries = NumberOfQueries();
		int myTask = myid + 1;
		while (myTask <= nqueries) {
			int from = QueryFrom(myTask);
			int to = QueryTo(myTask);
			order = 0;
			if (from != to) {
				int iterator1 = FirstNeighbor(from);
				int prev_iterator1 = from;
				int iterator2 = SecondNeighbor(from);
				int prev_iterator2 = from;
				order = 1;
				while (iterator1 != to && iterator2 != to) {
					if (prev_iterator1 == FirstNeighbor(iterator1)) {
						prev_iterator1 = iterator1;
						iterator1 = SecondNeighbor(iterator1);
					} else {
						prev_iterator1 = iterator1;
						iterator1 = FirstNeighbor(iterator1);
					}
					if (prev_iterator2 == FirstNeighbor(iterator2)) {
						prev_iterator2 = iterator2;
						iterator2 = SecondNeighbor(iterator2);
					} else {
						prev_iterator2 = iterator2;
						iterator2 = FirstNeighbor(iterator2);
					}
					order++;
				}
			}
			PutInt(0, myTask);
			PutInt(0, order);
			Send(0);
			myTask += nnodes;
		}
		if (!myid && nqueries) {
			for (int i = 0; i < nnodes; i++) {
				int myTask = i + 1;
				while (myTask <= nqueries) {
					Receive(i);
					int task = GetInt(i);
					int value = GetInt(i);
					answer[task] = value;
					myTask += nnodes;
				}
			}
			for (int i = 1; i <= nqueries; i++) {
				printf("%d\n", answer[i]);
			}
		}
	}
}