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
//Dominik Klemba
//Eeeee... to sie sypie. :/
//Nie bedzie punktow. =(
#include "message.h"
#include "kollib.h"
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <map>
#include <array>

using namespace std;

constexpr unsigned granica = 1250750;
typedef tuple<unsigned, unsigned> para;

vector<unsigned> centrum(const unsigned, const unsigned, const unsigned);
void dziecko(const unsigned, const unsigned, const unsigned);


int main() {
  ios_base::sync_with_stdio(false);
  //cerr << "Err\n";
  const unsigned liczba_uczniow = NumberOfStudents(),
                 moj_numer = MyNodeId();
  if(moj_numer == 0) {
    const vector<unsigned> odpowiedzi = centrum(liczba_uczniow,
                                                NumberOfQueries(),
                                                NumberOfNodes());
    copy(begin(odpowiedzi), end(odpowiedzi),
         ostream_iterator<unsigned>(cout, "\n"));
    return 0;
   }
  if(liczba_uczniow <= granica)
   return 0;
  dziecko(liczba_uczniow, moj_numer, NumberOfNodes());
 }


inline unsigned nowy(const unsigned przedostatni, const unsigned ostatni) {
  const unsigned a = FirstNeighbor(ostatni), b = SecondNeighbor(ostatni);
  return (przedostatni == a) ? b : a;
 }

inline unsigned dif(const unsigned i, const unsigned j) {
  //cerr << "| " << i << " - " << j <<" |\n";
  return (i>j) ? i - j : j - i;
 }


void dziecko(const unsigned liczba_uczniow, const unsigned moj_numer,
             const unsigned liczba_komputerow) {
  const unsigned w_przedziale = liczba_uczniow/(liczba_komputerow-1);
  const unsigned do_sprawdzenia = w_przedziale + ((moj_numer+1==liczba_komputerow)? liczba_uczniow % (w_przedziale): 0);
  //cerr <<"ds: "<< do_sprawdzenia <<'\n';
  const unsigned pierwszy_gorny = (liczba_komputerow-1)/2+1;
  const unsigned dostarczyciel = Receive(moj_numer == pierwszy_gorny ? 0 : moj_numer-1);
  unsigned przedostatni = GetInt(dostarczyciel);
  unsigned ostatni = GetInt(dostarczyciel);
  unsigned ii = GetInt(dostarczyciel);
  vector<para> uczniowie; uczniowie.reserve(do_sprawdzenia + 1);
  unsigned przerwa = 0;
  if(moj_numer + 1 == liczba_komputerow) {
    const unsigned dd = Receive(pierwszy_gorny-1);
    przerwa = GetInt(dd);
   }
  for(unsigned i = (moj_numer==1? 2 : 1); i <= do_sprawdzenia || moj_numer + 1 == liczba_komputerow; ++i) {
   //cerr << moj_numer; 
   const unsigned temp = nowy(przedostatni, ostatni);
    if(temp == przerwa)
     break;
    uczniowie.emplace_back(temp, ii);
    //cerr << temp << " na " << ii <<'\n';
    if(moj_numer < pierwszy_gorny)
     ++ii;
    else
     --ii;
    //cerr <<moj_numer <<" zawiera "<< temp << '\n';
    przedostatni = ostatni;
    ostatni = temp;
   }
  if(moj_numer == 1)
   uczniowie.emplace_back(1,0);
  if(moj_numer + 1 != liczba_komputerow && moj_numer + 1 != pierwszy_gorny) {
      //cerr << moj_numer << " wysyla!\n";
      PutInt(moj_numer+1, przedostatni);
      PutInt(moj_numer+1, ostatni);
      PutInt(moj_numer+1, ii);
      Send(moj_numer+1);
     }
   if(moj_numer + 1 == pierwszy_gorny) {
     PutInt(liczba_komputerow - 1, get<0>(uczniowie.back()));
     Send(liczba_komputerow - 1);
    }
  //cerr << moj_numer <<  " sortuje.\n";
  sort(begin(uczniowie), end(uczniowie));
  //cerr << moj_numer <<  " posortowal.\n";
  const unsigned liczba_pytan = NumberOfQueries();
  for(unsigned i = 1; i <= liczba_pytan; ++i) {
    const unsigned a = QueryFrom(i), b = QueryTo(i);
    auto it1 = lower_bound(begin(uczniowie), end(uczniowie),
                           make_tuple(a,0));
    auto it2 = lower_bound(begin(uczniowie), end(uczniowie),
                           make_tuple(b,0));
    if(get<0>(*it1) == a) {
      //cerr << a << "na" << get<1>(*it1) << '\n';
      PutInt(0, i);
      PutInt(0, get<1>(*it1));
      Send(0);
     }
    if(get<0>(*it2) == b) {
      //cerr << b << " do " << i << " od " << moj_numer << '\n';
      PutInt(0, i);
      PutInt(0, get<1>(*it2));
      Send(0);
     }
   }
 }

unsigned pomiedzy(para a, para b, unsigned w_przedziale) {
  //cerr << get<1>(a) << " ---> " << get<1>(b) << '\n';
  return dif(get<1>(a)+(get<0>(a)-1)*w_przedziale,get<1>(b) +(get<0>(b)-1) * w_przedziale);
 }

vector<unsigned> samotne_rozwiazanie(const unsigned liczba_uczniow) {
  map<unsigned, unsigned> odleglosci;
  unsigned przedostatni = 1, ostatni = FirstNeighbor(przedostatni);
  odleglosci[przedostatni] = 0;
  odleglosci[ostatni] = 1;
  for(unsigned i = 2; i < liczba_uczniow; ++i) {
    const unsigned temp = nowy(przedostatni, ostatni);
    odleglosci[temp] = i;
    przedostatni = ostatni;
    ostatni = temp;
   }
  const unsigned liczba_pytan = NumberOfQueries();
  vector<para> pytania; pytania.reserve(liczba_pytan);
  unsigned iij=0;
  generate_n(back_inserter(pytania), liczba_pytan,
             [&](){++iij; return make_tuple(QueryFrom(iij), QueryTo(iij));});
  vector<unsigned> odpowiedzi; odpowiedzi.reserve(liczba_pytan);
  transform(begin(pytania), end(pytania), back_inserter(odpowiedzi),
            [&](para x){unsigned dl = dif(odleglosci[get<0>(x)],odleglosci[get<1>(x)]);
                        return min(dl, liczba_uczniow - dl);});
  return odpowiedzi;
 }


vector<unsigned> centrum(const unsigned liczba_uczniow,
                         const unsigned liczba_pytan,
                         const unsigned liczba_komputerow) {
  if(liczba_uczniow <= granica)
   return samotne_rozwiazanie(liczba_uczniow);
  const unsigned pierwszy_gorny = (liczba_komputerow-1)/2+1;
  //cerr << "pierwszy_gorny = "<<pierwszy_gorny<<'\n';
  PutInt(pierwszy_gorny,FirstNeighbor(1));
  PutInt(pierwszy_gorny,1);
  PutInt(pierwszy_gorny,liczba_uczniow-1);
  Send(pierwszy_gorny);
  PutInt(1,SecondNeighbor(1));
  PutInt(1,1);
  PutInt(1,1);
  Send(1);
  vector<vector<para>> dane(liczba_pytan);
  for(unsigned liczba_pakietow = 0;liczba_pakietow < liczba_pytan*2; ++liczba_pakietow) {
    const unsigned dostarczyciel = Receive(-1);
    const unsigned nr = GetInt(dostarczyciel);
    const unsigned odleglosc = GetInt(dostarczyciel); //wzgledna
    //cerr << "od = " << dostarczyciel<<" + "<< odleglosc <<"("<<nr<<")" << '\n';
    dane[nr-1].push_back(make_tuple(dostarczyciel, odleglosc));
    //cerr << liczba_pakietow + 1 << " z " << liczba_pytan *2 << '\n';
   }
  vector<unsigned> wynik; wynik.reserve(liczba_pytan);
  for(auto& x : dane) {
    //cerr << "R: " << x.size() << '\n';
   unsigned dl = dif(get<1>(x[0]),get<1>(x[1])); 
   wynik.push_back(min(dl,liczba_uczniow - dl));
   }
  return wynik;
 }