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

int t[10000100],s[10000100];

int o(const void *a, const void *b)
{
  return t[*(int*)a]-t[*(int*)b];
}

int main()
{
  int n,m,i,j,p,q,a,b,c,d,*v,x,y;
  n=NumberOfStudents();
  m=NumberOfNodes();
  i=MyNodeId();
  if (m>n && i>0) return 0;
  if (m>n) p=0, q=n;
  else
  {
    p=n/m*i;
    q=i+1<m?n/m*(i+1):n;
  }
  if (p>0)
  {
    Receive(i-1);
    a=GetInt(i-1);
    b=GetInt(i-1);
  }
  else a=b=0;
  for (x=p;x<q;x++)
  {
    t[x-p]=a;
    s[x-p]=x-p;
    c=FirstNeighbor(a+1)-1;
    if (c==b) c=SecondNeighbor(a+1)-1;
    b=a, a=c;
  }
  if (q<n)
  {
    PutInt(i+1,a);
    PutInt(i+1,b);
    Send(i+1);
  }
  qsort(s,q-p,sizeof(*s),o);
  a=NumberOfQueries();
  for (b=0;b<a;b++)
  {
    c=QueryFrom(b+1)-1;
    v=(int*)bsearch(&c,s,q-p,sizeof(*s),o);
    PutInt(0,v?*v+p:-1);
    c=QueryTo(b+1)-1;
    v=(int*)bsearch(&c,s,q-p,sizeof(*s),o);
    PutInt(0,v?*v+p:-1);
    Send(0);
    if (i==0)
    {
      x=y=-1;
      for (j=0;j<(m>n?1:m);j++)
      {
        Receive(j);
        c=GetInt(j);
        c>=0?x=c:0;
        c=GetInt(j);
        c>=0?y=c:0;
      }
      c=(n+x-y)%n;
      d=(n+y-x)%n;
      printf("%d\n",c<d?c:d);
    }
  }
  return 0;
}