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
/*	Arek Wróbel - skater
 *
 *	Zadanie: Kółko informatyczne
 *	Konkurs: PA2014, runda 4B
 */
#include "message.h"
#include "kollib.h"

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define REP(I, N) for(int I=0; I<(N); ++I)
#define FOR(I, M, N) for(int I=(M); I<=(N); ++I)
#define FORD(I, M, N) for(int I=(M); I>=(N); --I)
#define FOREACH(IT, CON) for(__typeof(CON.begin()) IT=CON.begin(); IT!=CON.end(); ++IT)
#define ST first
#define ND second
#define MP make_pair
#define PB push_back
const int INF=1000000000;
const LL INFLL=1000000000000000000LL;

int numberOfNodes;
int myNodeId;
int N;
int Q;

PII queries[201];
VI t;
VI nr;

void make_distributed() {
	if (numberOfNodes > N)
		numberOfNodes = N;
	if (myNodeId >= numberOfNodes)
		exit(0);
	
}

inline int search(int v) {
	int pocz = 0;
	int sred;
	int kon = t.size();
	while (pocz + 1 < kon) {
		sred = (pocz+kon) >> 1;
		if (t[sred] > v)
			kon = sred;
		else
			pocz = sred;
	}
	return pocz;
}

void make_static() {
	if (myNodeId > 0)
		exit(0);
	
	FOR(i, 1, Q) {
		queries[i].ST = QueryFrom(i);
		queries[i].ND = QueryTo(i);
		t.PB(queries[i].ST);
		t.PB(queries[i].ND);
	}
	sort(t.begin(), t.end());
 	t.resize( distance(t.begin(), unique(t.begin(), t.end())) );
	nr.resize(t.size());
	
	if (t[0] == 1)
		nr[0] = 0;
	int prev = 1;
	int v = FirstNeighbor(1);
	for (int i = 1; v != 1; ++i) {
//		printf("(%d)\n", v);
		int x = search(v);
		if (t[x] == v)
			nr[x] = i;
		int next = FirstNeighbor(v);
		if (next == prev)
			next = SecondNeighbor(v);
		prev = v;
		v = next;
	}
//	FOR(i, 1, N) printf("%d: %d\n", i, nr[i]);
	FOR(i, 1, Q) {
		int a, b;
		a = nr[search( queries[i].ST )];
		b = nr[search( queries[i].ND )];
		if (a>b)
			swap(a, b);
		printf("%d\n", min(b-a, N-b+a));
	}
}

int main()
{
	numberOfNodes = NumberOfNodes();
	myNodeId = MyNodeId();
	N = NumberOfStudents();
	Q = NumberOfQueries();
	
/*	if (N >= 219000000)
		make_distributed();
	else
		make_static();
*/	make_static();
	
//	printf("KONIEC!\n");
	return 0;
}