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
101
102
103
104
105
106
107
108
109
#include "kollib.h"
#include "message.h"
#include <iostream>
#include <map>
#include <cmath>
#define REP(x,n) for(int x=0;x<(n);++x)
#define FOR(a,b,e) for(int a=b;a<=(e);++a)
#define VAR(x,n) __typeof(n) x = (n)
#define FOREACH(x,n) for(VAR(x,(n).begin());x!=(n).end();++x)
using namespace std;

map<int,int> needed;

long long start, stop;

void wyznacz(int prevprev, int prev, int ile) {
		int s1=prev, s2=prev;
		for(int i=0;i<ile;++i) { /// i to odległość od początku strefy
			if (needed.find(prev)!=needed.end()) {
				PutInt(0, prev);
				PutInt(0, start+i);
				Send(0);
			}
			s1 = FirstNeighbor(prev);
			s2 = SecondNeighbor(prev);
			if (prevprev==s1) {
				prevprev = prev;
				prev = s2;
			} else {
				prevprev = prev;
				prev = s1;
			}
		}
		if (MyNodeId()+1 == NumberOfNodes())
			return;
		PutInt(MyNodeId()+1, prevprev);
		PutInt(MyNodeId()+1, prev);
		Send(MyNodeId()+1);
}
void Recv() {
	int source = Receive(-1);
	int a = GetInt(source);
	int b = GetInt(source);
//	cout << "received " <<source<<": "<< a << " - " << b << endl;
	needed[a] = b;
}

int main() {
	int prev=1, prevprev=1,s1=1,s2=1;
	int n = NumberOfStudents();
	int m = NumberOfQueries();
	if (NumberOfNodes()==1) {
		int dist[n];
		for(int i=0;i<n;++i) {
			if (s1==s2) {
				dist[1] = 0;
				prev = s1 = FirstNeighbor(1);
			} else {
				dist[prev] = i;
				s1 = FirstNeighbor(prev);
				s2 = SecondNeighbor(prev);
				if (prevprev==s1) {
					prevprev = prev;
					prev = s2;
				} else {
					prevprev = prev;
					prev = s1;
				}
			}
		}
		for (int i = 1; i <= m; ++i) {
			int ans = abs(dist[QueryFrom(i)]-dist[QueryTo(i)]);
			cout << min(ans, n-ans) << endl;
		}
	} else {
		FOR(i,1,m) {
			needed[QueryFrom(i)]=-1;
			needed[QueryTo(i)]=-1;
		}
		start = ((long long)n)*MyNodeId()/NumberOfNodes();
		stop =  ((long long)n)*(MyNodeId()+1)/NumberOfNodes();
		if (MyNodeId()==0)
			wyznacz(1, 1, stop-start);
		else {
			Receive(MyNodeId()-1);
			int before = GetInt(MyNodeId()-1);
			int current= GetInt(MyNodeId()-1);
			wyznacz(before, current, stop-start);
		}
		map<int,int>::iterator it;
		if (!MyNodeId())
			for(int i=1;i<=m;++i) {
				it = needed.find(QueryFrom(i));
//				cout << "wait for " << it->first << endl;
				while (it->second == -1)
					Recv();
//				cout << "got " << it->first << " - " << it->second << endl;
				int wyn = it->second;
				it = needed.find(QueryTo(i));
//				cout << "wait for " << it->first << endl;
				while(it->second == -1)
					Recv();
//				cout << "got " << it->first << " - " << it->second << endl;
				wyn = abs(wyn-it->second);
				cout << min(wyn, n-wyn) << endl;
			}
	}
  return 0;
}