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
#include "message.h"

#include "kollib.h"
#include <iostream>
#include <map>
#include <set>
#include <list>

//ZLO!!!! 
//#include "kollib.c"
//ZLO!!!! 


using namespace std;

int main() {
	int numberOfNodes = NumberOfNodes();
	int myNodeId = MyNodeId();
	int numberOfStudents = NumberOfStudents();
	int numberOfQueries = NumberOfQueries();
	
	/*if(numberOfStudents < 100) {	//masakra....
		if(myNodeId == 0) {
			for(int i = 0; i < numberOfQueries; i++) {
				int queryFrom = QueryFrom(i+1);
				int queryTo = QueryTo(i+1);
				std::set<int> visitSet;
				int num = 0;
				
				visitSet.insert(queryFrom);
				int frontier[] = {queryFrom, queryFrom};
				while(visitSet.find(queryTo) == visitSet.end()) {
					for(int j = 0; j < 2; j++) {
						int first = FirstNeighbor(frontier[j]);
						int second = SecondNeighbor(frontier[j]);
						if(visitSet.find(first) == visitSet.end()) {
							frontier[j] = first;
						} else {
							frontier[j] = second;
						}
						visitSet.insert(frontier[j]);
					}
					num++;
				}
				cout << num << endl;
			}
		}
		return 0;
	}*/
	
	//POINTS_LENGTH
	int POINTS_LENGTH = 1000;
		//dziwny pomysl, zadziala tylko z pewnym prawdopodobienstwem....
	int points[] = {295606553, 1337580097, 1539083538, 1715052897, 1157170767, 100528013, 1608311427, 156343375, 1669156874, 833442669, 1195960662, 83294260, 1977485533, 882004357, 837901150, 215953934, 554396287, 1663381176, 1752121080, 795561525, 1442498415, 1407442804, 1446275849, 707854351, 858655614, 211065127, 1017555791, 134961281, 641137598, 944056241, 117133334, 1115216984, 987890102, 1137926410, 1892149147, 433684341, 1799896672, 1326712320, 530693940, 1488414218, 1959169194, 1361623359, 184510159, 53565215, 268874356, 1258295968, 718967801, 572376328, 824190873, 1306436009, 1935352235, 102379418, 1997121878, 497985974, 512067560, 254515054, 714534854, 1385311107, 1343090701, 1926846094, 892539968, 544083594, 1445421986, 62010115, 1090023445, 651357829, 25901525, 636654280, 50498212, 1478821698, 544700431, 1345342731, 1605464393, 713193693, 1635677965, 939863919, 1864695928, 349466551, 1950641973, 1408833072, 75530479, 1968355016, 1563207026, 1106770673, 308543205, 515035714, 1527878605, 557416236, 97504406, 756845901, 1188634770, 1182713284, 412317792, 105207358, 1904305310, 705558496, 1115015185, 1090459410, 89237892, 640126967, 255156301, 1151117110, 1481308054, 556590675, 55205824, 1017000211, 74352745, 320968639, 794024640, 1214891205, 449623643, 1982789586, 850668129, 1195876963, 1659863933, 393420865, 1313190398, 1046778085, 433557978, 184456802, 1851773406, 1969789415, 1255948595, 1877874896, 434553489, 1857749804, 1955710453, 1804101790, 463945674, 1213763092, 261298622, 423929886, 1251261187, 1066764269, 169020132, 25243419, 1192483242, 988432054, 806635362, 1959288228, 446943756, 1813874485, 861903177, 714064728, 599757763, 1197680702, 1230974147, 341534329, 114769825, 45215145, 1156348388, 1801898875, 1409509143, 564249938, 62775868, 706001777, 566509936, 1537926706, 491318960, 1947760382, 1889063472, 953106028, 808304957, 1318835951, 60229129, 405344, 770754048, 700894006, 757384043, 1880158010, 427888903, 1477892419, 1726499220, 248351729, 1941316574, 1025897125, 1639031065, 844870560, 63947237, 229103012, 1500710699, 1164849308, 1896810510, 181293831, 231520893, 899559828, 1852825904, 1821606610, 837480178, 1618264361, 884052174, 239695294, 410954394, 1708462460, 1320362188, 1912307534, 1113594362, 1661369330, 817462452, 1958079869, 945426634, 1393304349, 1118927645, 169356873, 263047140, 1125112299, 118714400, 777794269, 1427807202, 1615930496, 700662043, 1757456038, 1977368242, 105470241, 1657768362, 269410335, 268815770, 20993528, 1700126770, 606192819, 86259358, 322587427, 595176264, 1728690561, 72981091, 489517565, 661349321, 128770626, 1235675966, 469903450, 1368538695, 792316191, 1819713204, 686713024, 275611832, 1043029866, 1018601816, 1610461591, 474005901, 1608540112, 1187140325, 620391388, 319476362, 65523597, 657745566, 212670889, 1137335737, 956251000, 57762579, 1846890451, 490494939, 1316808505, 1627018135, 1021474719, 785256351, 1825370348, 1527601393, 10415734, 914417342, 1750790, 405383025, 448498644, 846947259, 746867892, 1905259497, 805897676, 895278374, 1358769520, 999463380, 199168047, 754642345, 1709418799, 1796180667, 55419290, 1493855063, 442875031, 824889286, 227416785, 879734322, 1463801922, 20288775, 459170746, 601342210, 535337193, 1703305057, 1454770593, 754948024, 1085880371, 1373788605, 1270765108, 1388202359, 1963608956, 845570114, 639278786, 834074816, 13550961, 1105183539, 628952988, 1446794318, 1245512938, 625016401, 659623035, 1924254725, 1596544561, 1256565841, 514647430, 90328657, 935881272, 1746926496, 1215957953, 1796339449, 537721959, 1161270258, 508494542, 316369584, 1913886107, 1642037033, 1252936921, 633731450, 277409505, 257605932, 106894495, 1406678436, 1289246442, 1605757047, 35824439, 689489177, 1200063966, 1492361813, 1845989911, 295042417, 1470149354, 58834058, 1126601195, 1005052520, 853134747, 631021627, 99346104, 10400012, 221117689, 1457851608, 1560133840, 1851313738, 67153983, 267015204, 266945499, 150027940, 971513223, 539681166, 136493993, 1276807698, 1192014657, 397902078, 18134047, 11921060, 311005373, 1048078336, 1175002641, 1775382305, 860042677, 465287550, 1267133067, 1475036196, 1418673421, 159684351, 1689433605, 401656902, 640663443, 164212778, 538479246, 1080882872, 702203861, 1733977835, 264178322, 1836769467, 420252257, 1421234631, 520537708, 1246017956, 1379177923, 1647877370, 174583292, 339575672, 1794271394, 1721782702, 561838699, 1079239494, 757009395, 1899129893, 1219364008, 1639419895, 581075152, 1110737289, 484468990, 32123223, 1726236549, 1673260020, 1267483110, 1262839026, 1535985328, 346086279, 1408401982, 762634715, 1511332081, 611640416, 1975895847, 443774935, 1802172518, 173251562, 1021890155, 1880271393, 1282006044, 210016102, 818547774, 1031565192, 1075232775, 1038020770, 1666545182, 1283029887, 1877998340, 1291103812, 700943552, 488954869, 562919331, 1238199142, 1513273302, 544636017, 1384303830, 1518780252, 1863164835, 693321693, 1053198655, 4001935, 1890449774, 1144556289, 1337655310, 1820430717, 1500373960, 350271384, 1879481709, 618612454, 570451457, 982587303, 1848087085, 584453554, 275952558, 1789591252, 294213399, 1582305359, 35741983, 1308986196, 85539321, 1459299950, 1468474221, 1891761515, 1141960481, 1119915506, 1113625685, 388116148, 686993082, 83742912, 1116143627, 756716550, 1356949041, 284964066, 1673231770, 296558738, 1629815464, 1284038806, 963108602, 1037022850, 780882446, 972714433, 1024254210, 1867556864, 427708592, 234841500, 804806349, 1642920460, 919966140, 1019299456, 1900376446, 233224554, 416782518, 53283711, 1345787871, 1127878259, 874957702, 179846897, 1680177995, 1374558342, 1640603357, 1609608336, 1619216605, 1115004268, 1271594738, 979067242, 1187325826, 815326024, 125363503, 1334823467, 537372877, 74694479, 1499616902, 1672332868, 253702524, 1383428258, 779983437, 179676409, 863673534, 322783889, 349874508, 827052936, 182829425, 1004266774, 1007790912, 1297356773, 1562824670, 1159565298, 543639930, 1985948541, 94657359, 111221301, 1702740610, 1245972892, 477692999, 756181348, 1695096788, 720448395, 113733158, 1237612132, 276094544, 963036275, 773799861, 1691118598, 1579553674, 1885954454, 1425389695, 1632748481, 146904112, 1257949784, 1981778711, 1519184267, 278769007, 723647135, 1362639203, 1554720389, 1520209450, 1467973918, 1355596967, 567060044, 1974781506, 221057319, 1062617855, 1311239354, 1024765277, 706544265, 398016939, 245741433, 520232494, 526033650, 1059775677, 347922401, 51730705, 1494878098, 831522442, 1178873262, 916594749, 986085549, 1377090386, 403483204, 822520117, 1179005747, 2276169, 213003, 1612442511, 1045015154, 1289198731, 920468403, 1215621302, 1340707277, 1572165129, 996270299, 870192982, 165937739, 1005605497, 1594512819, 1179012546, 1803782787, 857143134, 101632645, 1320898996, 1613421689, 1715532686, 432506479, 1123239721, 1947156738, 89371206, 451091321, 1115455485, 756863827, 1456929051, 1435646182, 1457746358, 1676611908, 782617724, 1562769161, 1477894321, 11581095, 1527563731, 177851634, 1609898152, 1652334279, 1351563426, 793879751, 408428327, 1838366315, 1454649720, 1578229919, 592726960, 142896879, 1500567535, 683835627, 1562697193, 1155800781, 693586679, 1195609351, 943042863, 536983109, 1031192488, 61792449, 102484176, 1337661504, 697427772, 611077311, 1211863148, 1613021426, 1320296909, 420286191, 1200929203, 1735946223, 106975928, 275796250, 1599812992, 1723811387, 1263946625, 476919168, 1306183461, 1325753758, 1805469371, 1331602819, 601876479, 1396857838, 1271621202, 1328820224, 615468846, 909509575, 1068154855, 1480306839, 1847214352, 594020198, 1491840700, 598073517, 1859807350, 1781518402, 1081460500, 1815838949, 1102422253, 4509019, 195767404, 1083828440, 765344523, 1303677748, 113816794, 1954407924, 1730175633, 1986108330, 1330979867, 1304731038, 1785226247, 1697459186, 359153505, 722956230, 1355245754, 1979373416, 264380925, 919336141, 1132214118, 1385911394, 1842583655, 1739923465, 960233736, 1103462550, 654922100, 1050154640, 1120104539, 1590876161, 1388225517, 626033955, 989991705, 233565549, 24059645, 860534356, 454017782, 1587139382, 818074458, 1388005624, 151287650, 168241622, 52259521, 1674475215, 908202023, 328664260, 1014169235, 425340491, 1744714223, 1794535664, 1779306475, 1443122529, 1387330801, 1506416474, 1963806594, 715772477, 908124814, 1422282597, 1964870505, 498943082, 881552187, 285089884, 794996721, 1789786014, 1732107604, 1047894344, 1015699875, 1955359620, 1384427833, 268318258, 700007447, 1190922831, 1212734866, 639785825, 1260419718, 714152050, 1087454566, 1443558983, 1386201037, 1734198203, 1273368623, 765090805, 511990953, 1972030838, 459890971, 835644180, 1170282403, 1500222310, 274086168, 1749255419, 1148780284, 1173365091, 1764232698, 682485307, 1043264420, 38170608, 19599257, 413887804, 1829702817, 1875073745, 546101729, 219311601, 1277222363, 21314838, 1240143715, 1854722260, 1955576220, 213854448, 493131416, 1841118041, 1074793008, 459270732, 269180717, 1883032748, 704194201, 1658673212, 549150152, 862344374, 869721992, 1425422900, 1149665916, 1808006570, 541419867, 1769499312, 1030929361, 394745549, 1699196365, 1066082084, 1675592306, 1780753535, 1235488038, 104424309, 700320503, 1276091468, 315353774, 785702508, 525232779, 776618140, 1069189534, 986159464, 336207458, 195864915, 1914771158, 1494510682, 1709074826, 1125450997, 306489084, 3534711, 546621264, 558935909, 582664106, 1489911847, 1932553407, 97052229, 1939421506, 384104983, 1360256646, 1106397682, 775690248, 1969112276, 844168317, 1564473444, 1784025228, 1287546274, 1701038091, 1162281403, 785853105, 52496858, 1806284929, 488203747, 748485848, 1339792792, 33287913, 172549949, 38225756, 420452301, 434917007, 214503051, 1423480116, 1893512060, 367573141, 433153974, 1736909505, 1307442827, 1444939973, 567157892, 1510592253, 1916480544, 872459983, 529184974, 754211828, 1038376454, 1580196563, 1218133151, 1609557095, 621472689, 588009851, 1437666230, 917455359, 114349507, 776365977, 1264580454, 1669862745, 85644363, 1826064683, 1605522612, 1938076056, 1946614921, 1045098530, 1160141523, 1305192242, 1534376722, 899914292, 1719286840, 1306927063, 583375621, 1379472124, 1527526178, 1438281369, 1155585587, 842914803, 115766243, 685234755, 199748891, 1013317301, 764914379, 39101756, 802740405, 29923767, 178882425, 1024082235, 854595904, 1234622329, 482394874, 1023001280, 1530443032, 1668684722, 1707635852, 1701465974, 994395692, 522291830, 589408430, 967696803, 1397324955, 1208996831, 1503441949, 481023850, 1839235312, 364234752, 1697343883, 1292587561, 481148377, 219854066, 548261514, 1336847350, 1447330610, 314245504, 1390434676, 929252602, 352926406, 633569905, 1340822573, 235054645, 1667086584, 884427920, 741157305, 543673021, 871152663, 674108753, 630127992, 930224277, 881062660, 846326176, 353838577, 1002215782, 1838761870, 884897891, 552413515, 113671754, 309209572, 341840566, 1247901649, 1794731147, 384781383, 315405939, 791521581, 1180550901, 1535649865, 1875244770, 1440911305, 811457891, 776791822, 603870263, 1046015258, 447228510, 1513822507, 1433398087, 120214438, 1781090577, 1355847497, 316715756, 829720279, 497927369, 1580874536, 125998338, 39965114, 1473889702, 112978139, 1377395054, 773579297, 1770366654, 1506724444, 1017686213, 456285739, 1869529598, 1739839551, 955632416, 133048887, 300148421, 1508062937, 959782796, 1986481916, 1981588553, 788775010, 1228254031, 604762806, 960124846, 1543109215, 1157025350, 280804643, 352150302, 462816814, 510266165, 147, 4567, 47, 751, 12, 20, 30};
	int pointsIdx = 0;
	int assignedPoints[numberOfNodes];
	int assignedPointsIdx = 0;
	std::set<int> assignedPointsSet;
	
	for(int i = 0; i < numberOfNodes; i++) {
		assignedPoints[i] = 0;
	}
	
	while(pointsIdx < POINTS_LENGTH && assignedPointsIdx < numberOfNodes) {
		int assignedPointsCandidate = points[pointsIdx] % numberOfStudents + 1;
		if(assignedPointsSet.find(assignedPointsCandidate) == assignedPointsSet.end()) {
			assignedPointsSet.insert(assignedPointsCandidate);
			assignedPoints[assignedPointsIdx++] = assignedPointsCandidate;
		}
		pointsIdx++;
	}
	
	if(assignedPoints[myNodeId] != 0) {
		assignedPointsSet.erase(assignedPoints[myNodeId]);
		
		std::set<int> queryElemSet;
		for(int i = 0; i < numberOfQueries; i++) {
			queryElemSet.insert(QueryFrom(i+1));
			queryElemSet.insert(QueryTo(i+1));
		}
		
		//std::set<int> visitSet;
		//visitSet.insert(assignedPoints[myNodeId]);
		int frontierNum[] = {0, 0};
		int frontier[] = {assignedPoints[myNodeId], assignedPoints[myNodeId]};
		
		std::list<int> queryElemFound;
		for(int j = 0; j < 2; j++) {
			int visitedElem = (j == 0 ? FirstNeighbor(assignedPoints[myNodeId]) : SecondNeighbor(assignedPoints[myNodeId]));
			//int num = 0;
			while(assignedPointsSet.find(frontier[j]) == assignedPointsSet.end()) {
				frontierNum[j]++;
				int first = FirstNeighbor(frontier[j]);
				int second = SecondNeighbor(frontier[j]);
				if(first != visitedElem) {
					visitedElem = frontier[j];
					frontier[j] = first;
				} else {
					visitedElem = frontier[j];
					frontier[j] = second;
				}
				//visitSet.insert(frontier[j]);
				if(queryElemSet.find(frontier[j]) != queryElemSet.end()) {
					queryElemFound.push_back(j);
					queryElemFound.push_back(frontierNum[j]);
					queryElemFound.push_back(frontier[j]);
				}
			}
		}
		
		PutInt(0, frontier[0]);
		PutInt(0, frontierNum[0]);
		PutInt(0, frontier[1]);
		PutInt(0, frontierNum[1]);
		PutInt(0, queryElemFound.size() / 3);
		Send(0);
		if(queryElemFound.size() / 3 > 0) {
			list<int>::iterator p = queryElemFound.begin();
			while(p != queryElemFound.end()) {
				PutInt(0, *p);
				p++;
			}
			Send(0);
		}
	}
	
	//ZZZZZZZZZZZZZ
	if(myNodeId == 0) {
		int frontiers[numberOfNodes][7];
		
		std::map<int,int> assignedToIdx;
		for(int i = 0; i < numberOfNodes; i++) {
			if(assignedPoints[i] != 0) {
				assignedToIdx.insert(std::make_pair(assignedPoints[i], i));
				Receive(i);
				frontiers[i][0] = GetInt(i);
				frontiers[i][1] = GetInt(i);
				frontiers[i][2] = GetInt(i);
				frontiers[i][3] = GetInt(i);
				frontiers[i][4] = GetInt(i);
				frontiers[i][5] = 0;	//dist od ucznia {0}
				frontiers[i][6] = 0;	//poprzedni ucznia {i}
				//cerr<<" " << "assignedPoints[" << i << "]= " << assignedPoints[i];
				//cerr<<" " << "frontiers[" << i << "]= " << frontiers[i][0] << "," << frontiers[i][1] << "," << frontiers[i][2] << "," << frontiers[i][3] << "," << frontiers[i][4] << "," << endl;
			}
		}
		
		//std::list<int> assignedOrderList;
		int assignedOrderListPos = assignedPoints[0];
		//int assignedOrderListLapsCnt = 0;
		int prevAssignedOrderListPos = -1;
		int way = 0;
		while(true) {
			//if(assignedOrderListPos == assignedPoints[0]) {
			//	assignedOrderListLapsCnt++;
			//}
			int index = (assignedToIdx.at(assignedOrderListPos));
			
			if(frontiers[index][5] == 0) {
				//cerr<<" " << "way[" << assignedOrderListPos << "]=" << way << ", poprzedni=" << prevAssignedOrderListPos << endl;
				frontiers[index][5] = way;
				frontiers[index][6] = prevAssignedOrderListPos;
			} else {
				break;
			}
			int nextPrevAssignedOrderListPos = assignedOrderListPos;
			
			//assignedOrderList.push_back(assignedOrderListPos);
			way += prevAssignedOrderListPos != frontiers[index][0] ? frontiers[index][1] : frontiers[index][3];
			assignedOrderListPos = (prevAssignedOrderListPos != frontiers[index][0] ? frontiers[index][0] : frontiers[index][2]);
			prevAssignedOrderListPos = nextPrevAssignedOrderListPos;
		}
		
		
		
		std::map<int,int> queryElemShifts;
		//queryElemShifts.insert(std::make_pair(elem, ??+num));
		
		for(int i = 0; i < numberOfNodes; i++) {
			if(assignedPoints[i] != 0 && frontiers[i][4] > 0) {
				Receive(i);
				for(int x = 0; x < frontiers[i][4]; x++) {
					//int index = (assignedToIdx.at(assignedOrderListPos));
					int j = GetInt(i);	//1-2
					int num = GetInt(i);	//num
					int elem = GetInt(i);	//frontier (element)
					
					int indexAssigned = (assignedToIdx.at(assignedPoints[i]));
					int indexFrontier = (assignedToIdx.at(frontiers[i][j*2]));
					//cerr << "   " << elem << " jest pomiedzy: " << assignedPoints[i]  << ".." <<  frontiers[i][j*2] << " dystans=" << frontiers[i][(j*2)+1] << endl;
					int elemShift;
					if(frontiers[indexFrontier][6] == assignedPoints[i]) {
						elemShift = frontiers[indexAssigned][5]+num;
					} else {
						elemShift = frontiers[indexFrontier][5]+(frontiers[i][(j*2)+1]-num);
					}
					if(elemShift > numberOfStudents) {
						elemShift -= numberOfStudents;
					}
					queryElemShifts.insert(std::make_pair(elem, elemShift));
				}
			}
		}
		for(int i = 0; i < numberOfQueries; i++) {
			int queryFrom = QueryFrom(i+1);
			int queryTo = QueryTo(i+1);
			if(queryFrom == queryTo) {
				cout << 0 << endl;
			} else {
				int dist = queryElemShifts.at(queryFrom) - queryElemShifts.at(queryTo);
				if(dist < 0) {
					dist += numberOfStudents;
				}
				if(numberOfStudents-dist < dist) {
					dist = numberOfStudents - dist;
				}
				cout << dist << endl;
			}
			
			//cerr<<" " << "od: " << queryFrom << " do: " << queryTo;
			//cerr<<" " << " przesuniecia: " << queryElemShifts.at(queryFrom) << " i: " << queryElemShifts.at(queryTo) << endl;
		}
		
	}//ZZZZZZZZZZZZZ
	return 0;
}