fork download
copy 
  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. //   if (inst == 0) {
  61. //     cout<<n<<endl;
  62. //   }
  63.   for (int i = 0; i < inst_num; i++) {
  64.     s = ((a * s) + b) % n;
  65.     st[i] = s + 1;
  66.     while (hash_starts[st[i] % kRange].pos) {
  67.       st[i] = st[i] % n + 1;
  68.     }
  69. //     if (inst == 0) {
  70. //       cout<<st[i]<<" ";
  71. //     }
  72.     hash_starts[st[i] % kRange] = HashPlace(st[i], i);
  73.   }
  74. //   if (inst == 0) {
  75. //     cout<<endl;
  76. //   }
  77.   //cerr<<inst<<" starts from "<<st[inst]<<endl;
  78.   int q_num = NumberOfQueries();
  79.   for (int i = 1; i <= q_num; i++) {
  80.     que[2 * i - 1] = QueryFrom(i);
  81.     que[2 * i] = QueryTo(i);
  82.     //cerr<<que[2 * i - 1]<<" "<<que[2 * i]<<endl;
  83.   }
  84.   for (int i = 1; i <= 2 * q_num; i++) {
  85.     hash_queries[que[i] % kRange].PB(HashPlace(que[i], i));
  86.   }
  87.   int act_v = st[inst];
  88.   int fir = FirstNeighbor(act_v);
  89.   int sec = SecondNeighbor(act_v);
  90.   int beg[] = {fir, sec};
  91.   for (int phase = 0; phase <= 1; phase++) {
  92.     vector<pair<int, int> > found_q;
  93.     int prev_v = st[inst];
  94.     act_v = st[inst];
  95.     for (auto p : hash_queries[act_v % kRange]) {
  96.       if (p.pos != act_v) {
  97.         continue;
  98.       }
  99.       //cerr<<"Proces nr "<<inst<<" znalazl "<<p.ind<<"-te q tzn. "<<p.pos<<endl;
  100.       found_q.push_back(MP(p.ind, 0));
  101.     }
  102.     act_v = beg[phase];
  103.     int act_dis = 1;
  104.     while (!Check(act_v)) {
  105.  
  106.       for (auto p : hash_queries[act_v % kRange]) {
  107.         if (p.pos != act_v) {
  108.           continue;
  109.         }
  110.         //cerr<<"Proces nr "<<inst<<" znalazl "<<p.ind<<"-te q tzn. "<<p.pos<<endl;
  111.         found_q.push_back(MP(p.ind, act_dis));
  112.       }
  113.       int new_v = FirstNeighbor(act_v) + SecondNeighbor(act_v) - prev_v;
  114.       prev_v = act_v;
  115.       act_v = new_v;
  116.       act_dis++;
  117.     }
  118.     int end_in = hash_starts[act_v % kRange].ind;
  119.     assert(st[end_in] == act_v);
  120.     PutInt(0, inst);
  121.     PutInt(0, end_in);
  122.     PutInt(0, act_dis);
  123.     PutInt(0, found_q.size());
  124.     for (auto p : found_q) {
  125.       //cerr<<"Hejka"<<inst<<endl;
  126.       PutInt(0, p.first);
  127.       PutInt(0, p.second);
  128.     }
  129.     Send(0);
  130.   }
  131.  
  132.   if (inst != 0) {
  133.     return 0;
  134.   }
  135.   int max_len = 0;
  136.   for (int i = 0; i < inst_num; i++) {
  137.     if (died[i]) {
  138.       continue;
  139.     }
  140.     for (int zz = 1; zz <= 2; zz++) {
  141.       Receive(i);
  142.       int a = GetInt(i);
  143.       int b = GetInt(i);
  144.       int len = GetInt(i);
  145.       max_len = max(max_len, len);
  146.       //cout<<len<<endl;
  147.       int found_q_num = GetInt(i);
  148.       //cerr<<"czytam message (od "<<i<<") "<<a<<" "<<b<<" "<<len<<" "<<found_q_num<<endl;
  149.       vector<pair<int, int> > found_q;
  150.       for (int j = 0; j < found_q_num; j++) {
  151.         int fir = GetInt(i);
  152.         int sec = GetInt(i);
  153.         //cerr<<"znalezione "<<fir<<" "<<sec<<endl;
  154.         found_q.PB(MP(fir, sec));
  155.       }
  156.       edges[a].PB(Edge(b, len, found_q));
  157.     }
  158.   }
  159.   Dfs(0, 0, 0);
  160.   cerr<<1.0 * max_len / n<<endl;
  161.   /* for (int i = 1; i <= 2 * q_num; i++) {
  162.     cout<<pos[i]<<" ";
  163.   }
  164.   cout<<endl; */
  165.   for (int i = 1; i <= q_num; i++) {
  166.  
  167.     int diff = abs(pos[2 * i - 1] - pos[2 * i]);
  168.     //cout<<min(diff, n - diff)<<endl;
  169.   }
  170.  
  171.   return 0;
  172. }
  173.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1:20: fatal error: kollib.h: No such file or directory
 #include "kollib.h"
                    ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/6heC9R
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!