oj.uz

Submission #573918

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

# Verdict Execution time Memory Grader output
1 Correct 122 ms 2548 KB Output is correct
2 Correct 181 ms 2604 KB Output is correct
3 Correct 278 ms 2612 KB Output is correct
4 Correct 164 ms 2648 KB Output is correct
5 Correct 249 ms 2668 KB Output is correct
6 Correct 528 ms 3468 KB Output is correct
7 Correct 1132 ms 2652 KB Output is correct

Subtask #2
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Partially correct 1774 ms 2552 KB Output is partially correct
2 Partially correct 890 ms 2668 KB Output is partially correct
3 Partially correct 1075 ms 2540 KB Output is partially correct
4 Partially correct 1979 ms 2556 KB Output is partially correct
5 Partially correct 1670 ms 2604 KB Output is partially correct
6 Incorrect 612 ms 712 KB Not correct
7 Halted 0 ms 0 KB -