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
#include "kollib.h"
#include <cstdio>
#include "message.h"
#include <vector>
#include <map>

using namespace std;

int main() {
/*  for (int i = 1; i <= NumberOfQueries(); ++i) {
    if (QueryFrom(i) == QueryTo(i))
      cout << 0 << endl;
    else if (QueryTo(i) == FirstNeighbor(QueryFrom(i)) || QueryTo(i) == SecondNeighbor(QueryFrom(i)))
      cout << 1 << endl;
    else
      cout << 2 << endl;
  }
*/
int inst = MyNodeId();
int lens[NumberOfNodes()+2];
if (inst ==0){
int len = NumberOfStudents()/NumberOfNodes() + (NumberOfStudents()%NumberOfNodes()>0 ? 1 : 0);
//printf("len: %d\n", len);
int last = -1, pos = 1, t = -1;
if (len<3) len = 3;
int a = 1, nodeid = 0;
PutInt(nodeid, pos);
for (int i=0;i<NumberOfStudents();i++) {
if (last != FirstNeighbor(pos)) t = FirstNeighbor(pos); else t = SecondNeighbor(pos);
last = pos; pos = t;
if (a < 2) PutInt(nodeid, pos);
a++;
if (len == a) {PutInt(nodeid, a); lens[nodeid]=a; a = 0; Send(nodeid);nodeid++;}
}
if (a>1) {PutInt(nodeid, a-1); lens[nodeid] = a-1; a = 0; Send(nodeid); nodeid++;}
for (int j=nodeid;j<NumberOfNodes();j++) {lens[j] = 0; PutInt(j, 0); PutInt(j, 0); PutInt(j, 0); Send(j);}
} // nodeid 0 chodzenie

Receive(0);
int start = GetInt(0);
int next = GetInt(0);
int len = GetInt(0);
//printf("otrzymano %d: %d %d %d\n", inst, start, next, len);
if (len==0) return 0;

int last = start; int pos = next; int t=-1;
vector<int> v;
v.push_back(last); v.push_back(pos);
for (int i=0;i<len-2;i++) {
if (last != FirstNeighbor(pos)) t = FirstNeighbor(pos); else t = SecondNeighbor(pos);
last = pos; pos = t;
v.push_back(pos);
}
//printf("v %d: ", inst);for (int i=0;i<v.size();i++) printf("%d ", v[i]); printf("\n");
map<int, int> mapa;
for(int i=0;i<v.size();i++) mapa[v[i]] = i;
int result[NumberOfQueries()+3];
for(int i=1;i<=NumberOfQueries();i++) {
if (mapa.find(QueryFrom(i)) != mapa.end() && mapa.find(QueryTo(i)) != mapa.end()) 
{result[i] = mapa[QueryTo(i)] - mapa[QueryFrom(i)]; if (result[i]<0) result[i]=-result[i];}
else if (mapa.find(QueryFrom(i)) != mapa.end()) {result[i] = len-mapa[QueryFrom(i)];}
else if (mapa.find(QueryTo(i)) != mapa.end()) {result[i] = -mapa[QueryTo(i)]-1;}
else result[i] = 0; 
}
//printf("Result %d: ", inst); for (int i=1;i<=NumberOfQueries();i++) printf("%d ", result[i]); printf("\n");
for (int i=1;i<=NumberOfQueries();i++){
PutInt(0, i);
PutInt(0, result[i]);
Send(0);
}

if (inst == 0) {
int matka[NumberOfNodes()+15][NumberOfQueries()+15];
for (int i=0;i<NumberOfNodes();i++) {
//printf("Getting %d...\n", i);
for (int q=0;q<NumberOfQueries();q++) 
if (lens[i]==0) matka[i][q+1]=0;
else{Receive(i);
int query = GetInt(i);
int v = GetInt(i);
matka[i][query] = v;}

}
//for (int i=0;i<NumberOfNodes();i++) {for (int q=1;q<=NumberOfQueries();q++) printf("%d ", matka[i][q]); printf(" | %d\n", lens[i]);}
for (int q=1;q<=NumberOfQueries();q++) {
int result = 0, t=0;
for (int n=0;n<NumberOfNodes();n++) 
if (matka[n][q]>0 && result == 0) result = matka[n][q];
else if (matka[n][q] == 0 && result>0) t += lens[n];
else if (matka[n][q]<0 && result>0) result += t - matka[n][q] -1 ;
else if (matka[n][q]<0 && result==0) result = lens[n] + matka[n][q] +1;
else if (matka[n][q]>0 && result>0) result += t + lens[n] - matka[n][q];

printf("%d\n", min(result, NumberOfStudents()-result));
//printf("%d\n", result);
}
}

/*for (int i=0;i<NumberOfQueries();i++) {printf("%d\n", tmp[i]);}}*/
return 0;
}