Advertisement
Guest User

Untitled

a guest
May 16th, 2014
313
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.29 KB | None | 0 0
  1. #include "kollib.h"
  2. #include "message.h"
  3. #include <iostream>
  4. #include <cassert>
  5. #include <vector>
  6. #define MP make_pair
  7. #define PB push_back
  8. using namespace std;
  9. typedef long long ll;
  10. const int kMaxQ = 404;
  11. int que[kMaxQ];
  12. int pos[kMaxQ];
  13. const int kRange = 1813632;
  14. vector<pair<int, int> > hash_que[kRange];
  15. const int kMaxInst = 1e2 + 4;
  16. int st[kMaxInst];
  17. struct HashPlace {
  18. int pos;
  19. int ind;
  20. HashPlace (int start_, int ind_) : pos(start_), ind(ind_) {}
  21. HashPlace () : pos(0), ind(0) {}
  22. };
  23. HashPlace hash_starts[kRange];
  24. bool Check(int act_v) {
  25. return hash_starts[act_v % kRange].pos == act_v;
  26. }
  27. vector<HashPlace> hash_queries[kRange];
  28. int died[kMaxInst];
  29. struct Edge {
  30. int nei;
  31. int len;
  32. vector<pair<int, int> > found_q;
  33. Edge(int n_, int l_, vector<pair<int, int> >& f_) : nei(n_), len(l_), found_q(f_) {}
  34. };
  35. vector<Edge> edges[kMaxInst];
  36. int vis[kMaxInst];
  37. void Dfs(int v, int dis_from_start, int dep) {
  38. vis[v] = 1;
  39. for (auto& e : edges[v]) {
  40. if (!vis[e.nei] || (e.nei == 0 && dep > 1)) {
  41. for (auto p : e.found_q) {
  42. pos[p.first] = dis_from_start + p.second;
  43. }
  44. Dfs(e.nei, dis_from_start + e.len, dep + 1);
  45. }
  46. }
  47. }
  48. int main() {
  49. //cerr<<"j"<<endl;
  50. int n = NumberOfStudents();
  51. int inst_num = min(n, NumberOfNodes());
  52. int inst = MyNodeId();
  53. if (inst >= inst_num) {
  54. return 0;
  55. }
  56. ll s, a, b, k;
  57. s = 127654389 % n;
  58. a = 364995323;
  59. b = 837322103;
  60. k = 584380613;
  61. //cerr<<"j"<<endl;
  62. for (int i = 0; i < inst_num; i++) {
  63. s = (((a * s) + b) / k) % n;
  64. st[i] = s + 1;
  65. while (hash_starts[st[i] % kRange].pos) {
  66. st[i] = st[i] % n + 1;
  67.  
  68. }
  69. hash_starts[st[i] % kRange] = HashPlace(st[i], i);
  70. }
  71. //cerr<<inst<<" starts from "<<st[inst]<<endl;
  72. int q_num = NumberOfQueries();
  73. for (int i = 1; i <= q_num; i++) {
  74. que[2 * i - 1] = QueryFrom(i);
  75. que[2 * i] = QueryTo(i);
  76. //cerr<<que[2 * i - 1]<<" "<<que[2 * i]<<endl;
  77. }
  78. for (int i = 1; i <= 2 * q_num; i++) {
  79. hash_queries[que[i] % kRange].PB(HashPlace(que[i], i));
  80. }
  81. int act_v = st[inst];
  82. int fir = FirstNeighbor(act_v);
  83. int sec = SecondNeighbor(act_v);
  84. int beg[] = {fir, sec};
  85. for (int phase = 0; phase <= 1; phase++) {
  86. vector<pair<int, int> > found_q;
  87. int prev_v = st[inst];
  88. act_v = st[inst];
  89. for (auto p : hash_queries[act_v % kRange]) {
  90. if (p.pos != act_v) {
  91. continue;
  92. }
  93. //cerr<<"Proces nr "<<inst<<" znalazl "<<p.ind<<"-te q tzn. "<<p.pos<<endl;
  94. found_q.push_back(MP(p.ind, 0));
  95. }
  96. act_v = beg[phase];
  97. int act_dis = 1;
  98. while (!Check(act_v)) {
  99.  
  100. for (auto p : hash_queries[act_v % kRange]) {
  101. if (p.pos != act_v) {
  102. continue;
  103. }
  104. //cerr<<"Proces nr "<<inst<<" znalazl "<<p.ind<<"-te q tzn. "<<p.pos<<endl;
  105. found_q.push_back(MP(p.ind, act_dis));
  106. }
  107. int new_v = FirstNeighbor(act_v) + SecondNeighbor(act_v) - prev_v;
  108. prev_v = act_v;
  109. act_v = new_v;
  110. act_dis++;
  111. }
  112. int end_in = hash_starts[act_v % kRange].ind;
  113. assert(st[end_in] == act_v);
  114. PutInt(0, inst);
  115. PutInt(0, end_in);
  116. PutInt(0, act_dis);
  117. PutInt(0, found_q.size());
  118. for (auto p : found_q) {
  119. //cerr<<"Hejka"<<inst<<endl;
  120. PutInt(0, p.first);
  121. PutInt(0, p.second);
  122. }
  123. Send(0);
  124. }
  125.  
  126. if (inst != 0) {
  127. return 0;
  128. }
  129.  
  130. for (int i = 0; i < inst_num; i++) {
  131. if (died[i]) {
  132. continue;
  133. }
  134. for (int zz = 1; zz <= 2; zz++) {
  135. Receive(i);
  136. int a = GetInt(i);
  137. int b = GetInt(i);
  138. int len = GetInt(i);
  139. int found_q_num = GetInt(i);
  140. //cerr<<"czytam message (od "<<i<<") "<<a<<" "<<b<<" "<<len<<" "<<found_q_num<<endl;
  141. vector<pair<int, int> > found_q;
  142. for (int j = 0; j < found_q_num; j++) {
  143. int fir = GetInt(i);
  144. int sec = GetInt(i);
  145. //cerr<<"znalezione "<<fir<<" "<<sec<<endl;
  146. found_q.PB(MP(fir, sec));
  147. }
  148. edges[a].PB(Edge(b, len, found_q));
  149. }
  150. }
  151. Dfs(0, 0, 0);
  152. /* for (int i = 1; i <= 2 * q_num; i++) {
  153. cout<<pos[i]<<" ";
  154. }
  155. cout<<endl; */
  156. for (int i = 1; i <= q_num; i++) {
  157.  
  158. int diff = abs(pos[2 * i - 1] - pos[2 * i]);
  159. cout<<min(diff, n - diff)<<endl;
  160. }
  161.  
  162. return 0;
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement