Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "kollib.h"
- #include "message.h"
- #include <iostream>
- #include <cassert>
- #include <vector>
- #define MP make_pair
- #define PB push_back
- using namespace std;
- typedef long long ll;
- const int kMaxQ = 404;
- int que[kMaxQ];
- int pos[kMaxQ];
- const int kRange = 1813632;
- vector<pair<int, int> > hash_que[kRange];
- const int kMaxInst = 1e2 + 4;
- int st[kMaxInst];
- struct HashPlace {
- int pos;
- int ind;
- HashPlace (int start_, int ind_) : pos(start_), ind(ind_) {}
- HashPlace () : pos(0), ind(0) {}
- };
- HashPlace hash_starts[kRange];
- bool Check(int act_v) {
- return hash_starts[act_v % kRange].pos == act_v;
- }
- vector<HashPlace> hash_queries[kRange];
- int died[kMaxInst];
- struct Edge {
- int nei;
- int len;
- vector<pair<int, int> > found_q;
- Edge(int n_, int l_, vector<pair<int, int> >& f_) : nei(n_), len(l_), found_q(f_) {}
- };
- vector<Edge> edges[kMaxInst];
- int vis[kMaxInst];
- void Dfs(int v, int dis_from_start, int dep) {
- vis[v] = 1;
- for (auto& e : edges[v]) {
- if (!vis[e.nei] || (e.nei == 0 && dep > 1)) {
- for (auto p : e.found_q) {
- pos[p.first] = dis_from_start + p.second;
- }
- Dfs(e.nei, dis_from_start + e.len, dep + 1);
- }
- }
- }
- int main() {
- //cerr<<"j"<<endl;
- int n = NumberOfStudents();
- int inst_num = min(n, NumberOfNodes());
- int inst = MyNodeId();
- if (inst >= inst_num) {
- return 0;
- }
- ll s, a, b, k;
- s = 127654389 % n;
- a = 364995323;
- b = 837322103;
- k = 584380613;
- //cerr<<"j"<<endl;
- for (int i = 0; i < inst_num; i++) {
- s = (((a * s) + b) / k) % n;
- st[i] = s + 1;
- while (hash_starts[st[i] % kRange].pos) {
- st[i] = st[i] % n + 1;
- }
- hash_starts[st[i] % kRange] = HashPlace(st[i], i);
- }
- //cerr<<inst<<" starts from "<<st[inst]<<endl;
- int q_num = NumberOfQueries();
- for (int i = 1; i <= q_num; i++) {
- que[2 * i - 1] = QueryFrom(i);
- que[2 * i] = QueryTo(i);
- //cerr<<que[2 * i - 1]<<" "<<que[2 * i]<<endl;
- }
- for (int i = 1; i <= 2 * q_num; i++) {
- hash_queries[que[i] % kRange].PB(HashPlace(que[i], i));
- }
- int act_v = st[inst];
- int fir = FirstNeighbor(act_v);
- int sec = SecondNeighbor(act_v);
- int beg[] = {fir, sec};
- for (int phase = 0; phase <= 1; phase++) {
- vector<pair<int, int> > found_q;
- int prev_v = st[inst];
- act_v = st[inst];
- for (auto p : hash_queries[act_v % kRange]) {
- if (p.pos != act_v) {
- continue;
- }
- //cerr<<"Proces nr "<<inst<<" znalazl "<<p.ind<<"-te q tzn. "<<p.pos<<endl;
- found_q.push_back(MP(p.ind, 0));
- }
- act_v = beg[phase];
- int act_dis = 1;
- while (!Check(act_v)) {
- for (auto p : hash_queries[act_v % kRange]) {
- if (p.pos != act_v) {
- continue;
- }
- //cerr<<"Proces nr "<<inst<<" znalazl "<<p.ind<<"-te q tzn. "<<p.pos<<endl;
- found_q.push_back(MP(p.ind, act_dis));
- }
- int new_v = FirstNeighbor(act_v) + SecondNeighbor(act_v) - prev_v;
- prev_v = act_v;
- act_v = new_v;
- act_dis++;
- }
- int end_in = hash_starts[act_v % kRange].ind;
- assert(st[end_in] == act_v);
- PutInt(0, inst);
- PutInt(0, end_in);
- PutInt(0, act_dis);
- PutInt(0, found_q.size());
- for (auto p : found_q) {
- //cerr<<"Hejka"<<inst<<endl;
- PutInt(0, p.first);
- PutInt(0, p.second);
- }
- Send(0);
- }
- if (inst != 0) {
- return 0;
- }
- for (int i = 0; i < inst_num; i++) {
- if (died[i]) {
- continue;
- }
- for (int zz = 1; zz <= 2; zz++) {
- Receive(i);
- int a = GetInt(i);
- int b = GetInt(i);
- int len = GetInt(i);
- int found_q_num = GetInt(i);
- //cerr<<"czytam message (od "<<i<<") "<<a<<" "<<b<<" "<<len<<" "<<found_q_num<<endl;
- vector<pair<int, int> > found_q;
- for (int j = 0; j < found_q_num; j++) {
- int fir = GetInt(i);
- int sec = GetInt(i);
- //cerr<<"znalezione "<<fir<<" "<<sec<<endl;
- found_q.PB(MP(fir, sec));
- }
- edges[a].PB(Edge(b, len, found_q));
- }
- }
- Dfs(0, 0, 0);
- /* for (int i = 1; i <= 2 * q_num; i++) {
- cout<<pos[i]<<" ";
- }
- cout<<endl; */
- for (int i = 1; i <= q_num; i++) {
- int diff = abs(pos[2 * i - 1] - pos[2 * i]);
- cout<<min(diff, n - diff)<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement