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
#include "kollib.h"
#include "message.h"
#include <cstdio>
#include <map>
#include <cstdlib>
#include <vector>
#include <ctime>
using namespace std;
map<int, int> pos;
int main() {
    srand(7);
    int x = MyNodeId();
    //printf("Running %d\n", x);
    int n = NumberOfStudents();
    int m = NumberOfNodes();
    if (m == 1) {
        pos[1] = 0;
        int a = 1, last = -1;
        while (true) {
            int b = FirstNeighbor(a);
            if (b == last) b = SecondNeighbor(a);
            if (b == 1) break;
            pos[b] = pos[a]+1;
            last = a;
            a = b;
        }
        int q = NumberOfQueries();
        for (int t=1; t<=q; t++) {
            int ans = pos[QueryFrom(t)] - pos[QueryTo(t)];
            if (ans < 0) ans = -ans;
            if (n-ans < ans) ans = n-ans;
            printf("%d\n", ans);
        }
        return 0;
    }
    if (x >= n) return 0;
    if (m > n) m = n;
    int start;
    for (int i=0; i<m; i++) {
        int a = (rand() % n) + 1;
        if (pos.count(a)) { i--; continue; }
        if (i == x) {
            pos[a] = 0;
            start = a;
        } else pos[a] = n+i;
    }
    int a = start, last = -1, prev = -1, next = -1;
    if (x) {
        prev = Receive(-1);
        last = GetInt(prev);
    }
    while (true) {
        int b = FirstNeighbor(a);
        if (b == last) b = SecondNeighbor(a);
        if (pos[b] >= n) {
            next = pos[b]-n;
            PutInt(next, a);
            Send(next);
            break;
        } else {
            pos[b] = pos[a]+1;
            last = a;
            a = b;
        }
    }
    /*printf("%d: ", x);
    for (map<int,int>::iterator it=pos.begin(); it!=pos.end(); it++) if (it->second < n) printf("%d ", it->first);
    printf("\n");*/
    int size = pos[a]+1;
    if (!x) {
        prev = Receive(-1);
        GetInt(prev);
    }
    int q = NumberOfQueries();
    for (int t=1; t<=q; t++) {
        int a = QueryFrom(t);
        int b = QueryTo(t);
        if (pos.count(a) && pos[a] < n) {
            //printf("(%d) %d found (%d); sending %d to %d\n", t, a, x, size-pos[a],next);
            PutInt(next, size-pos[a]);
            Send(next);
            Receive(prev);
            int ans = GetInt(prev) + pos[a];
            if (pos.count(b) && pos[b] < n) ans = pos[b]>pos[a]?pos[b]-pos[a]:pos[a]-pos[b];
            if (n-ans < ans) ans = n-ans;
            PutInt(0, ans);
            Send(0);
        } else {
            Receive(prev);
            int ans = GetInt(prev);
            int send = ans+size;
            if (pos.count(b) && pos[b] < n) send = size-pos[b];
            PutInt(next, send);
            //printf("(%d) %d received %d; sending %d to %d\n", t,x,ans,send,next);
            Send(next);
        }
        if (!x) {
            int r = Receive(-1);
            //printf("Received answer %d\n", r);
            printf("%d\n", GetInt(r));
            PutChar(next, 0);
            Send(next);
        } else {
            Receive(prev);
            GetChar(prev);
            if (next != 0) {
                PutChar(next, 0);
                Send(next);
            }
        }
    }
    //printf("Ending %d\n", x);
    return 0;
}