Submission #573921

#	Time	Username	Problem	Language	Result	Execution time	Memory
573921		lumibons	Flight to the Ford (BOI22_communication)	C++17	15 / 100	1221 ms	1988 KiB

communication

#include <bitset>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include "communication.h"

#define sz(x) ((int) (x).size())

using namespace std;

const int hashSize = 1000, hashLength = 22, additionalHashs = 4;
typedef bitset<hashLength> bh;

bool hashsComputed = false;
bh xHash[hashSize];

void init() {
  srand(42);
}

void newHashs() {
  int bits = 32 - __builtin_clz(RAND_MAX);
  for (int i = 0; i < hashSize; i++)
    for (int j = 0; j < (hashLength + bits - 1) / bits; j++) {
      int r = rand();
      for (int k = 0; k < bits && j * bits + k < hashLength; k++)
        xHash[i][j * bits + k] = (r >> k) & 1;
    }
}

vector<int> matches(bh h) {
  vector<int> r;
  for (int i = 0; i < hashSize; i++) {
    bh d = h ^ xHash[i];
    if ((d & (d >> 1)).none())
      r.push_back(i);
  }
  return r;
}

void writeHash(int x) {
  newHashs();
  for (int i = 0; i < hashLength; i++)
    send(xHash[x][i]);
}

vector<int> readHash() {
  bh h;
  for (int i = 0; i < hashLength; i++)
    h[i] = receive();
  newHashs();
  return matches(h);
}

int ha(int k, int l) {
	return (112211221ll*k+843243243ll*l) % 1000000009;
}

void encode(int N, int X) {
  init();
  N--, X--;
  int Y = X;
  while (N) {
    writeHash(X % hashSize);
    N /= hashSize, X /= hashSize;
  }
  int h = 42424242;
  for (int i = 0; i < additionalHashs; i++) {
    h = ha(h, Y);
    writeHash(h % hashSize);
  }
}

void alternatives(vector<vector<int>> &xs, vector<int> &r, int N, int X = 0, int m = 1, int i = 0) {
  if (i == (int) xs.size()) {
    if (X < N)
      r.push_back(X);
    return;
  }
  for (int x : xs[i])
    alternatives(xs, r, N, X + m * x, m * hashSize, i + 1);
}

std::pair<int, int> decode(int N) {
  init();
  int n = N - 1;
  vector<vector<int>> xs;
  while (n) {
    xs.push_back(readHash());
    n /= hashSize;
  }
  vector<int> x;
  alternatives(xs, x, N);
  vector<int> h(sz(x), 42424242);
  while (sz(x) > 2) {
    vector<int> nx, nh, m = readHash();
    for (int i = 0; i < sz(x); i++) {
      h[i] = ha(h[i], x[i]);
      int v = h[i] % hashSize;
      int j = (int)(lower_bound(m.begin(), m.end(), v) - m.begin());
      if (j < sz(m) && m[j] == v)
        nx.push_back(x[i]), nh.push_back(h[i]);
    }
    x = nx, h = nh;
  }
  return {x[0] + 1, x.back() + 1};
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 85