oj.uz

Submission #573921

# Submission time Handle Problem Language Result Execution time Memory
573921 2022-06-07T12:09:08 Z lumibons Flight to the Ford (BOI22_communication) C++17
15 / 100
 1221 ms 1988 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1708 KB Output is correct
2 Correct 139 ms 1772 KB Output is correct
3 Correct 140 ms 1828 KB Output is correct
4 Correct 67 ms 1780 KB Output is correct
5 Correct 106 ms 1712 KB Output is correct
6 Correct 302 ms 1844 KB Output is correct
7 Correct 572 ms 1828 KB Output is correct

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1101 ms 1968 KB Output is partially correct
2 Partially correct 469 ms 1820 KB Output is partially correct
3 Partially correct 800 ms 1788 KB Output is partially correct
4 Partially correct 1221 ms 1720 KB Output is partially correct
5 Partially correct 1088 ms 1988 KB Output is partially correct
6 Incorrect 613 ms 200 KB Not correct
7 Halted 0 ms 0 KB -