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
#include <cmath>
#include <cstdio>
#include <map>
#include <set>
#include "kollib.h"
#include "message.h"
using namespace std;

#define REP(i,n) for (int i = 0; i < (n); ++i)
#define FORD(i,a,b) for (int i = (b) - 1; i >= (a); --i)
typedef long long LL;

int otherNeighbor(int i, int j) {
	int k = FirstNeighbor(i);
	if (k == j) k = SecondNeighbor(i);
	return k;
}

int forward(int& i, int& j) {
	int k = otherNeighbor(i, j);
	j = i;
	i = k;
}

void sendPosition(int i, int p) {
	PutInt(0, i);
	PutInt(0, p);
	Send(0);
}

void receivePosition(int& i, int& p) {
	int s = Receive(-1);
	i = GetInt(s);
	p = GetInt(s);
}

int main() {
	set<int> queries;
	int qq = NumberOfQueries();
	REP(q,qq) {
		queries.insert(QueryFrom(q + 1));
		queries.insert(QueryTo(q + 1));
	}
	int n = NumberOfStudents();
	int k = NumberOfNodes();
	int j = MyNodeId();
	int start = LL(n) * j / k, end = LL(n) * (j + 1) / k;
	int last = 0, current = 1;
	if ((j << 1) < k) {
		REP(i,end) {
			if (i >= start && queries.find(current) != queries.end()) sendPosition(current, i);
			forward(current, last);
		}
	} else {
		last = otherNeighbor(current, last);
		forward(current, last);
		FORD(i,start,n) {
			if (i < end && queries.find(current) != queries.end()) sendPosition(current, i);
			forward(current, last);
		}
	}
	if (!MyNodeId()) {
		int qq2 = queries.size();
		map<int, int> pos;
		REP(q,qq2) {
			int i, p;
			receivePosition(i, p);
			pos[i] = p;
		}
		REP(q,qq) {
			int diff = abs(pos[QueryFrom(q + 1)] - pos[QueryTo(q + 1)]);
			diff = min(diff, n - diff);
			printf("%d\n", diff);
		}
	}
}