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
#include <cstdio>
#include <vector>
#include <ctime>
#include <cstdlib>
#include "kollib.h"
#include "message.h"
using namespace std;

int ID, n, m, q;

void prog1(){
    if (ID!=0) return;

    // Wczytywanie danych
    vector<pair<int,int> > N;
    vector<int> RANK;
    N.resize(n); RANK.resize(n, -1);
    for(int i=0; i<n; ++i){
        N[i].first = FirstNeighbor(i+1)-1;
        N[i].second = SecondNeighbor(i+1)-1;
    }

    // Obliczanie rankingu
    int prev = 0;
    int curr = N[prev].first;

    RANK[prev] = 0;
    RANK[curr] = 1;
    for(int i=0; i<n-2; ++i){
        int next = N[curr].first;
        if (next==prev) next = N[curr].second;
        RANK[next] = RANK[curr]+1;
        prev = curr;
        curr = next;
    }

    // Wczytywanie i obsluga zapytan
    int m = NumberOfQueries();
    for(int i=0; i<m; ++i){
        int a = RANK[QueryFrom(i+1)-1];
        int b = RANK[QueryTo(i+1)-1];
        printf("%d\n", min((a-b+n)%n,(b-a+n)%n));
    }
}

void prog2(){

    // Praca Slave'a
    for(int test_id=ID+1; test_id<=q; test_id += m){
        int from = QueryFrom(test_id);
        int to = QueryTo(test_id);

        int result = 0;
        if (from != to){
            result = 1;
            int prev = from;
            int curr; if (rand()%2==0) curr = FirstNeighbor(from); else curr = SecondNeighbor(from);
            while(curr != to){
                int X = FirstNeighbor(curr);
                int Y = SecondNeighbor(curr);
                int next = X; if (next == prev) next = Y;

                ++result;
                prev = curr;
                curr = next;
            }
            result = min(result, n-result);
        }

        PutInt(0, result);
    
    }
    if (ID<q) Send(0);

    // Praca Master'a
    if (ID != 0) return;
    vector<int> results(q, -1);
    for(int worker_id=0; worker_id<m; ++worker_id){
        if (worker_id+1>q) continue;
        Receive(worker_id);
        int j = worker_id;
        while(j+1<=q){
            results[j] = GetInt(worker_id);
            j+=m;
        }
    }
    for (int i=0; i<results.size(); ++i) printf("%d\n", results[i]);
}

int main(){
    srand(time(NULL));
    ID = MyNodeId();
    n = NumberOfStudents();
    q = NumberOfQueries();
    m = NumberOfNodes();

    long long size = n; size = size*q; size = size/(2*m);
    if (n>20000000) prog2(); else prog1();
}