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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <random>
#include <map>
#include <unordered_map>
#include "message.h"
using namespace std;
#define VAR(n,v) typeof(v) n=(v)
#define REP(i,n) for(int i=1; i<=(n); ++i)
#define FOR(i,a,b) for(VAR(i,a); i!=(b); ++i)
#define FORE(it,t) FOR(it,t.begin(),t.end())
typedef vector<int> vi;
#define pb push_back
typedef pair<int,int> pii;
typedef unordered_map<int,int> hii;
#define mp make_pair
#define st first
#define nd second
typedef long long ll;
#define INF 1000000001
#define sz size()
#define ALL(t) (t).begin(),(t).end()
#define SC(a) scanf("%d", &a)
#define GET(a) int a; SC(a)
#define ISDEBUG 1
#define dprintf(...) if(ISDEBUG) \
	{printf("\033[31m"); printf(__VA_ARGS__); printf("\033[0m");}
template <class It> void dptab(It b, It e, const char* f="%d ")
	{if(ISDEBUG) {for(It it=b; it!=e; ++it) dprintf(f, *it); dprintf("\n"); }}
#define QUERY 123
#define SOLUTION 69
#define KILL 666
#define COUNT 90

#include "kollib.h"
/*
vi ST = {1, 6, 4, 5, 3, 8, 7, 10, 9, 2};
#define N ((int)(ST.sz))
int NumberOfStudents() {return N;}
pii ns(int v) {
	int i;
	for(i=0; i<N; ++i)
		if(ST[i]==v) break;
	return mp(ST[(i+1)%N], ST[(i+N-1)%N]);
}
int FirstNeighbor(int i) 	{return min(ns(i).st, ns(i).nd);}
int SecondNeighbor(int i) 	{return max(ns(i).st, ns(i).nd);;}
vector<pii> QUERIES = {{7,6}, {4,9}, {4,4}, {9,4}};
int NumberOfQueries() {return QUERIES.sz;}
int QueryFrom(int i) {return QUERIES[i-1].st;}
int QueryTo(int i) {return QUERIES[i-1].nd;}*/



int sendto(int target, const vi& nums) {
	for(int num: nums)
		PutInt(target, num);
	//printf("SEND");
	//for(auto a: nums)
	//	printf(" %d", a);
	//printf("\n");
	Send(target);
}
int recv() {return Receive(-1);}
int next(int from, int at) {
	int f = FirstNeighbor(at), s = SecondNeighbor(at);
	if(f!=from && s!=from)
		printf("%d -> %d -> (%d, %d)\n", from, at, f, s);
	return f+s - from;
}


int n, m;

int getrandom(int nodeid) {
	srand(time(0)+nodeid*127);
	return rand()%n + 1;
}

void solved(int i, int dist) {
	sendto(0, {SOLUTION, i, min(dist, n-dist)});
}
void pass(int i, int to, int neigh, int before, int dist) {
	//printf("PASS i=%d to=%d before=%d dist=%d\n", i, to, before, dist);
	sendto(neigh, {QUERY, i, to, before, dist});
}

int start;
hii starts;
hii rev_starts;
hii left, right;
int left_neigh, right_neigh;
int left_przedo, right_przedo;
hii solutions;

int received;
int total_count;


void handle_solution(int i, int dist, int nodes) {
	//if(solutions.count(i) && dist != solutions[i])
	//	printf("LOL %d %d->%d\n", i, dist, solutions[i]);
	solutions[i] = dist;
	++received;
	//printf("solutions %d/%d\n", received, total_count);
	if(received == total_count) {
		REP(solid, m)
			printf("%d\n", solutions[solid]);
		FOR(node,0,nodes)
			sendto(node, {KILL});
	}
}

void solve_using(hii& dir, hii& odir, int przedo, int neigh, int from, int to, int i, int dist) {
	//if(dist)
	//	printf("solve_using przedo=%d neigh=%d from=%d to=%d i=%d dist=%d\n", przedo, neigh, from, to, i, dist);
	if(!dir.count(from)) return;
	if(dir.count(to))
		solved(i, dist + abs(dir[from] - dir[to]));
	else if(odir.count(to))
		solved(i, dist + dir[from] + odir[to]);
	else {
		int pos = dir[from];
		int neigh_start_pos = dir[rev_starts[neigh]];
		//printf("delta dist = %d - %d = %d\n", neigh_start_pos, pos, neigh_start_pos - pos);
		pass(i, to, neigh, przedo, dist + neigh_start_pos - pos);
	}
}

//int is_mine(int from, hii& dir, hi)

void handle_pass(int i, int to, int before, int dist) {
	//printf("HANDLE PASS i=%d to=%d before=%d dist=%d\n", i, to, before, dist);
	//printf("handle_pass %d,%d %d, %d %d\n", before, left_neigh, right_neigh, left[before], right[before]);
	if(left.count(before) && left[before] == 1) {
		//printf("PASS right to %d\n", right_neigh);
		solve_using(right, left, right_przedo, right_neigh, start, to, i, dist);
	}
	else if(right.count(before) && right[before] == 1) {
		//printf("PASS left to %d\n", left_neigh);
		solve_using(left, right, left_przedo, left_neigh, start, to, i, dist);
	}
	else {
		//printf("WUUT? i=%d to=%d before=%d dist=%d\n", i, to, before, dist);
		solved(i, INF);
	}
}

int fill(hii& dir, int at, int& przedo) {
	int len=0;
	int from = start;
	dir[start] = len++;
	przedo = start;
	dir[at] = len++;
	while(!starts.count(at)) {
		przedo = at;
		//printf("at %d->%d\n", from, at);
		int new_at = next(from, at);
		from = at;
		at = new_at;
		dir[at] = len++;
	}
	//printf("found border at %d with %d\n", at, starts[at]);
	return starts[at];
}

void comp(int nodeid, int nodes) {
	//printf("%d/%d\n", nodeid, nodes);
	n = NumberOfStudents();
	m = NumberOfQueries();

	FOR(node,0,nodes) {
		if(node == nodeid) {
			do {
				start = getrandom(nodeid);
			} while(starts.count(start));
			FOR(i,0,nodes)
				sendto(i, {start});
			//printf("start %d->%d\n", nodeid, start);
		}
		int from = Receive(node);
		int where = GetInt(from);
		starts[where] = from;
		rev_starts[from] = where;
	}
	//	for(auto& kv: starts)
	/*if(!nodeid) {
			printf("%d->%d\n", kv.nd, kv.st);
	}*/
		
	
	left_neigh = fill(left, FirstNeighbor(start), left_przedo);
	right_neigh = fill(right, SecondNeighbor(start), right_przedo);
	//printf("<%d %d %d>\n", left_neigh, nodeid, right_neigh);

	int count = 0;
	REP(i,m) {
		int from = QueryFrom(i);
		count += left.count(from) + right.count(from);
	}
	sendto(0, {count});

	if(!nodeid) {
		FOR(node, 0, nodes) {
			Receive(node);
			total_count += GetInt(node);
		}
	}

	REP(i, m) {
		int from = QueryFrom(i), to = QueryTo(i);
		//printf("query: <%d,%d>\n", from, to);
		solve_using(left, right, left_przedo, left_neigh, from, to, i, 0);
		solve_using(right, left, right_przedo, right_neigh, from, to, i, 0);
	}
	while(true) {
		int from = recv();
		int type = GetInt(from);
		if(type == QUERY) {
			int i=GetInt(from), to=GetInt(from), before=GetInt(from), dist=GetInt(from);
			handle_pass(i, to, before, dist);
		}
		else if(type == SOLUTION) {
			int a=GetInt(from), b=GetInt(from);
			handle_solution(a, b, nodes);
		}
		else if(type == KILL) {
			//printf("exiting %d\n", nodeid);
			break;
		}
		//else
		//	printf("unknown type %d\n", type);
	}
}


int main() {
	int nodes = min(NumberOfNodes(), NumberOfStudents()/2);
	int node = MyNodeId();
	if(node < nodes)
		comp(node, nodes);
}