Submission #987766

#	Time	Username	Problem	Language	Result	Execution time	Memory
987766		abczz	Two Transportations (JOI19_transportations)	C++14	0 / 100	239 ms	664 KiB

Azer

#include "Azer.h"
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define ll long long

using namespace std;

namespace {
  vector <int> dist;
  vector <ll> ord;
  vector <array<ll, 2>> adj[2000];
  bool b = 0;
  ll p_cost = 0, queue_sz = 0, qx = 0, qy = 0, gx, gy, resp = -1;
  priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
  void print(ll u, ll x) {
    for (int i=x-1; i>=0; --i) {
      SendA((bool)(u & (1LL<<i)));
    }
  }
  void search(ll u) {
    for (auto [v, x] : adj[u]) {
      if (dist[v] > dist[u] + x) {
        dist[v] = dist[u] + x;
        pq.push({dist[v], v});
      }
    }
  }
  void solve() {
    auto u = ord.back();
    ord.pop_back();
    //cout << u << "*\n";
    if (!u) {
      gx = gy = 0;
      while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        if (dist[u] != w) continue;
        gx = w, gy = u;
        //cout << w << " " << u << "?\n";
        //cout << p_cost << endl;
        print(w-p_cost, 9);
        print(u, 11);
        break;
      }
      if (!gy) {
        //cout << gx << " " << gy << "?\n";
        print(gx, 9);
        print(gy, 11);
      }
      b = 1;
    }
    else b = 0;
  }
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  srand(-1);
  dist.resize(N);
  for (int i=0; i<N; ++i) {
    if (i) dist[i] = (ll)1e9;
    ord.push_back(rand() & 1);
  }
  for (int i=0; i<A; ++i) {
    adj[U[i]].push_back({V[i], C[i]});
    adj[V[i]].push_back({U[i], C[i]});
  }
  search(0);
  solve();
}

void ReceiveA(bool r) {
  //cout << "A\n";
  if (b) {
    if (resp == -1) {
      if (r) {
        //cout << "bitA" << " " << r << endl;
        dist[gy] = gx;
        search(gy);
        p_cost = gx;
        solve();
      }
      else resp = 0;
      return;
    }
    if (queue_sz < 9) qx = 2 * qx + (ll)r;
    else qy = 2 * qy + (ll)r;
    queue_sz = (queue_sz + 1) % 20;
    if (queue_sz) return;
    qx += p_cost;
    dist[qy] = qx;
    search(qy);
    if (qy != gy && gy) pq.push({gx, gy});
    p_cost = qx;
    solve();
    resp = -1, qx = qy = 0;
    return;
  }
  if (queue_sz < 9) qx = 2 * qx + (ll)r;
  else qy = 2 * qy + (ll)r;
  queue_sz = (queue_sz + 1) % 20;
  if (queue_sz) return;
  ll x = 0, y = 0;
  qx += p_cost;
  while (!pq.empty()) {
    auto [w, u] = pq.top();
    pq.pop();
    if (dist[u] != w) continue;
    x = w, y = u;
    break;
  }
  //cout << x << " " << y << "!\n";
  //cout << qx << " " << qy << "a\n";
  if (!y && !qy) return;
  if (!y) x = 1e9;
  if (!qy) qx = 1e9;
  if (qx <= x) {
    dist[qy] = qx;
    search(qy);
    if (qy != y && y) pq.push({x, y});
    SendA(1);
    p_cost = qx;
  }
  else {
    dist[y] = x;
    search(y);
    SendA(0);
    //cout << qx << " " << qy << "no\n";
    print(x-p_cost, 9);
    print(y, 11);
    p_cost = x;
  }
  //cout << p_cost << endl;
  qx = qy = 0;
  solve();
}

std::vector<int> Answer() {
  return dist;
}

Baijan

#include "Baijan.h"
#include <vector>
#include <iostream>
#include <queue>
#include <array>
#define ll long long

using namespace std;

namespace {
  vector <int> dist;
  vector <ll> ord;
  vector <array<ll, 2>> adj[2000];
  bool b = 0;
  ll p_cost = 0, queue_sz = 0, qx = 0, qy = 0, gx, gy, resp = -1;
  priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
  void print(ll u, ll x) {
    for (int i=x-1; i>=0; --i) {
      SendB((bool)(u & (1LL<<i)));
    }
  }
  void search(ll u) {
    for (auto [v, x] : adj[u]) {
      if (dist[v] > dist[u] + x) {
        dist[v] = dist[u] + x;
        pq.push({dist[v], v});
      }
    }
  }
  void solve() {
    auto u = ord.back();
    ord.pop_back();
    //cout << u << "**\n";
    if (u) {
      gx = gy = 0;
      while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        if (dist[u] != w) continue;
        gx = w, gy = u;
        //cout << w << " " << u << "??\n";
        //cout << p_cost << endl;
        print(w-p_cost, 9);
        print(u, 11);
        break;
      }
      if (!gy) {
        //cout << gx << " " << gy << "??\n";
        print(gx, 9);
        print(gy, 11);
      }
      b = 1;
    }
    else b = 0;
  }
}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
  srand(-1);
  dist.resize(N);
  for (int i=0; i<N; ++i) {
    if (i) dist[i] = (ll)1e9;
    ord.push_back(rand() & 1);
  }
  for (int i=0; i<B; ++i) {
    adj[S[i]].push_back({T[i], D[i]});
    adj[T[i]].push_back({S[i], D[i]});
  }
  search(0);
  solve();
}

void ReceiveB(bool r) {
  //cout << "B\n";
  if (b) {
    if (resp == -1) {
      //cout << "bitB " << r << endl;
      if (r) {
        dist[gy] = gx;
        search(gy);
        //cout << gx << " " << gy << "aidja\n";
        p_cost = gx;
        solve();
      }
      else resp = 0;
      return;
    }
    if (queue_sz < 9) qx = 2 * qx + (ll)r;
    else qy = 2 * qy + (ll)r;
    queue_sz = (queue_sz + 1) % 20;
    if (queue_sz) return;
    qx += p_cost;
    dist[qy] = qx;
    if (qy != gy && gy) pq.push({gx, gy});
    search(qy);
    p_cost = qx;
    solve();
    resp = -1;
    return;
  }
  if (queue_sz < 9) qx = 2 * qx + (ll)r;
  else qy = 2 * qy + (ll)r;
  queue_sz = (queue_sz + 1) % 20;
  if (queue_sz) return;
  ll x = 0, y = 0;
  qx += p_cost;
  while (!pq.empty()) {
    auto [w, u] = pq.top();
    pq.pop();
    if (dist[u] != w) continue;
    x = w, y = u;
    break;
  }
  //cout << x << " " << y << "!!\n";
  //cout << qx << " " << qy << "b\n";
  if (!y && !qy) return;
  if (!y) x = 1e9;
  if (!qy) qx = 1e9;
  if (qx <= x) {
    dist[qy] = qx;
    search(qy);
    if (qy != y && y) pq.push({x, y});
    SendB(1);
    p_cost = qx;
  }
  else {
    dist[y] = x;
    search(y);
    SendB(0);
    print(x-p_cost, 9);
    print(y, 11);
    p_cost = x;
  }
  //cout << p_cost << endl;
  qx = qy = 0;
  solve();
}

Compilation message (stderr)

Azer.cpp: In function 'void {anonymous}::search(long long int)':
Azer.cpp:23:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for (auto [v, x] : adj[u]) {
      |               ^
Azer.cpp: In function 'void {anonymous}::solve()':
Azer.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |         auto [w, u] = pq.top();
      |              ^
Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:108:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |     auto [w, u] = pq.top();
      |          ^

Baijan.cpp: In function 'void {anonymous}::search(long long int)':
Baijan.cpp:23:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for (auto [v, x] : adj[u]) {
      |               ^
Baijan.cpp: In function 'void {anonymous}::solve()':
Baijan.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |         auto [w, u] = pq.top();
      |              ^
Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:109:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |     auto [w, u] = pq.top();
      |          ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 38
• Subtask 5: 0 / 14
• Subtask 6: 0 / 10
• Subtask 7: 0 / 16