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
110
111
112
113
114
115
116
117
118
119
120
#include "kollib.h"
#include "message.h"
#include <stdio.h>
#include <set>
#include <map>
#include <random>
using namespace std;
set<int> v;
map<int,int> iv;
int ivn = 0;

int gv;
int go(int f, int d) {
	int n, i = 1;
	n = d ? FirstNeighbor(f) : SecondNeighbor(f);
//	if (v.count(f)) { gv = f; return 0; }
	for (;!v.count(n);i++) {
		int n1 = FirstNeighbor(n);
		if (n1 == f) n1 = SecondNeighbor(n);
		f = n;
		n = n1;
	}
	gv = n;
	return i;
}

#define M 200
#define N 1000
int qf[M], qt[M];
int fn[N], fnd[N];
int sn[N], snd[N];
int vi[N];
int idx[N];


int go2() {
	int n, i, f = 0;
	n = fn[f];
	i = fnd[f];
	idx[n] = i;
//	printf("index of %d is %d (%d)\n", vi[n], i, n);
	while (n) {
		int n1 = fn[n];
		int d1 = fnd[n];
		if (n1 == f) n1 = sn[n], d1 = snd[n];
		i += d1;
		f = n;
		n = n1;
		idx[n] = i;
//		printf("index of %d is %d\n", vi[n], i);
	}
	return i;
}

void add(int i) {
	if (v.count(i)) return;
	v.insert(i);
	iv[i] = ivn;
	vi[ivn++] = i;
}

int main() {
	int i;
	int n = NumberOfStudents();
	int m = NumberOfQueries();
	default_random_engine rnd(1337);
	uniform_int_distribution<int> dist(1, n);
	for (i = 0; i < 500; i++) {
		add(dist(rnd));
	}
	for (i = 0; i < m; i++) {
  		qf[i] = QueryFrom(i+1);
  		qt[i] = QueryTo(i+1);
  		add(qf[i]);
  		add(qt[i]);
  	}
  	for (i = MyNodeId(); i < ivn; i+=NumberOfNodes()) {
  		PutInt(0, i);
  		int j = go(vi[i], 0);
  		PutInt(0, j);
  		PutInt(0, iv[gv]);
//  		printf ("from %d left is %d in %d\n", vi[i], gv, j);
  		j = go(vi[i], 1);
  		PutInt(0, j);
  		PutInt(0, iv[gv]);
//  		printf ("from %d right is %d in %d\n", vi[i], gv, j);
  	}
  	PutInt(0, -1);
  	Send(0);
  	if (!MyNodeId()) {
  		for (i = 0; i < NumberOfNodes(); i++) {
  			int rn = Receive(-1);
  			int j;
  			while ((j = GetInt(rn)) >= 0) {
  				fnd[j] = GetInt(rn);
  				fn[j] = GetInt(rn);
  				snd[j] = GetInt(rn);
  				sn[j] = GetInt(rn);
  			}
  		}
  		go2();
  		for (i = 0; i < m; i++) {
  			int r = idx[iv[qf[i]]] - idx[iv[qt[i]]];
  			if (r < 0) r = -r;
  			if (r > n / 2) r = n - r;
			printf("%d\n", r);
		}
	}
#if 0
  	v.clear();
  	for (i = 0; i < m; i++) {
  		v.insert(qt[i]);
		int r = go(qf[i], 0);
		if (r > n / 2) r = n - r; 
		printf("%d\n", r);
      	v.clear();
	}
#endif
	return 0;
}