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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
#define ll long long

#include "kollib.h"
#include "message.h"

struct koles{int n, p;};
vector<koles> tab;
vector<koles>::iterator it,it2;
bool fc(const koles &a, const koles &b) {return a.n<b.n;}
bool fc2(const koles &a, int bn) {return a.n<bn;}
int ans[201];

int main(int argc, char** argv) {
	ios_base::sync_with_stdio(0);	
	// przygotowanie
	ll NS = NumberOfStudents();
	int NN = min(NumberOfStudents(),NumberOfNodes());
	int MN = MyNodeId();
	if (MN>NN-1) return 0;
	int p = MN*NS / NN;
	int k = (MN+1)*NS / NN;
	int d = k-p;
	tab.resize(d);
	//cout << MyNodeId() << ": " << p+1 << " " << k << '\n';
	if (MN==0){
		int s0 =-1,s=1,s2;
		for (int i=0;i<d;i++) {
			tab[i].n=s; tab[i].p=i;
			s2 = FirstNeighbor(s);
			if (s2==s0) s2=SecondNeighbor(s);
			s0=s; s=s2;
		}
		PutInt(1,s);PutInt(1,s0);Send(1);
		sort(tab.begin(),tab.end(),fc);
		//cout << MyNodeId()<<": "; for (int i=0;i<d;i++) cout << tab[i].n << " na " << tab[i].p << ", "; cout << '\n';
		Receive(NN-1);
		//cout << "Wszyscy gotowi\n";
		for (int i=1;i<NN;i++) Send(i);
	} else {
		int inst = Receive(MN-1);
		int s=GetInt(inst),s0=GetInt(inst),s2;
		for (int i=0;i<d;i++) {
			tab[i].n=s; tab[i].p=i;
			s2 = FirstNeighbor(s);
			if (s2==s0) s2=SecondNeighbor(s);
			s0=s; s=s2;
		}
		if (MN==NN-1)
			Send(0);
		else {
			PutInt((MN+1)%NN,s);PutInt((MN+1)%NN,s0);Send((MN+1)%NN);
		}
		sort(tab.begin(),tab.end(),fc);
		Receive(0);
		//cout << MyNodeId() << " ok\n";
	}
	//cout << MyNodeId()<<": "; for (int i=0;i<d;i++) cout << tab[i].n << " na " << tab[i].p << ", "; cout << '\n';
	
	// zapytania
	// 3 - szukam, z - zapytanie, odl - odleglosc na razie
	// 2 - odpowiedz od razu, z - zapytanie, odl - odpowiedz
	// 1 - odpowiedz jedna, z - zapytanie, odl - odpowiedz
	int NQ=NumberOfQueries();
	int ile_odp=0;
	for (int z=1;z<=NQ;z++) { //wysylanie
		ans[z]=NS+1;
		int a=QueryFrom(z);
		int b=QueryTo(z);
		it = lower_bound(tab.begin(),tab.end(),a,fc2);
		if (it!=tab.end() && it->n==a) {
			//cout << MN << " ja pytam o " << a << " do " << b <<  '\n';
			it2 =lower_bound(tab.begin(),tab.end(),b,fc2);
			if (it!=tab.end() && it2->n==b) { //oba w tym samym
				int odl =abs((it->p) - (it2->p)); 
				//cout << MN << " mam też " << b << " ww odleglosci " << odl << '\n';
				if (MN==1) {
					ans[z] = min(ans[z],odl);
					ile_odp +=2;
				} else {
					PutChar(1,2); PutInt(1,z); PutInt(1,odl); Send(1);
				}
			} else { //nie ma w tym samym, więc nadajemy w dwie strony
				int prawy = MN == NN-1 ? 0 : MN+1;
				int lewy  = MN == 0 ? NN-1 : MN-1;
				int odl = it->p;
				PutChar(prawy,3); PutInt(prawy,z); PutInt(prawy,d-odl); Send(prawy);
				PutChar(lewy,3); PutInt(lewy,z); PutInt(lewy,odl+1); Send(lewy);
				//cout << MN << "wysylam w prawo do " << prawy << " odl " << d-odl << '\n';
				//cout << MN << "wysylam w lewo do " << lewy << " odl " << odl+1 << '\n';
			}
		}
	}
	//przekazywanie i odbieranie
	//cout << MN << ": koniec\n";
   
	while (true) {
		int inst=Receive(-1);
		char typ = GetChar(inst); int z,odl;
		if (typ!=0) { z = GetInt(inst); odl=GetInt(inst);}		
		//cout << MN << ": odebrano od " << inst << " typ=" << (int)typ << " z=" << z << " odl=" << odl << '\n';
		 
		if (typ==3) { //szukanie
			bool zlewej = (inst+1)%NN == MN;
			int b=QueryTo(z);
			it = lower_bound(tab.begin(),tab.end(),b,fc2);
			if (it!=tab.end() && it->n==b) { //znaleziony
				if (zlewej) // z lewej
					odl += it->p;
				else
					odl += d-1 - (it->p);
				PutChar(1,1); PutInt(1,z);PutInt(1,odl); Send(1);
 			} else {
 				int nast = zlewej ? (MN+1)%NN : (MN-1+NN)%NN;
 				odl += d;
				PutChar(nast,3); PutInt(nast,z); PutInt(nast,odl); Send(nast);
				//cout << MN << ": wysylam dalej do " << nast << " odl " << d-odl << '\n';
 			}
		} else if (typ==1 || typ==2){ //odpowiedz tylko dla 1
			ans[z] = min(ans[z],odl);
			ile_odp += typ;			
			//cout << MN << ": mam odpowiedzi " << ile_odp << '\n';
			if (ile_odp==2*NQ) {
				for (int i=0;i<NN;i++) {
					PutChar(i,0); Send(i);
				}
			}
		} else { // typ ==0
			break;
		}
		
	}
	
	if (MN==1) 
		for (int z=1;z<=NQ;z++)
			cout << ans[z] << '\n';




	return 0;
}