Submission #573918

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

communication

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

using namespace std;

const int hashSize = 32000, hashLength = 80;
typedef bitset<hashLength> bh;

bool hashsComputed = false;
bh xHash[hashSize];

void computeHashs() {
  if (hashsComputed)
    return;
  hashsComputed = true;
  srand(42);
  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) {
  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();
  return matches(h);
}

void encode(int N, int X) {
  computeHashs();
  N--, X--;
  int checksum = 0;
  while (N) {
    int x = X % hashSize;
    writeHash(x);
    checksum += x;
    N /= hashSize, X /= hashSize;
  }
  writeHash(checksum % hashSize);
}

void solve(vector<vector<int>> &xs, vector<int> &cs, vector<int> &r, int N, int X = 0, int checksum = 0, int m = 1, int i = 0) {
  if (i == (int) xs.size()) {
    if (X < N && find(cs.begin(), cs.end(), checksum % hashSize) != cs.end())
      r.push_back(X);
    return;
  }
  for (int x : xs[i]) {
    solve(xs, cs, r, N, X + m * x, checksum + x, m * hashSize, i + 1);
    if ((int) r.size() == 2)
      return;
  }
}

std::pair<int, int> decode(int N) {
  computeHashs();
  int n = N - 1;
  vector<vector<int>> xs;
  while (n) {
    xs.push_back(readHash());
    n /= hashSize;
  }
  vector<int> cs = readHash(), r;
  solve(xs, cs, r, N);
  return {r[0] + 1, r.back() + 1};
}

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