Submission #990786

#	Time	Username	Problem	Language	Result	Execution time	Memory
990786		jakobrs	Ancient Machine 2 (JOI23_ancient2)	C++17	99 / 100	37 ms	604 KiB

ancient2

#include "ancient2.h"

#include <bitset>
#include <memory>
#include <numeric>
#include <string>
#include <vector>

void gauss(std::bitset<1001> (&matrix)[1000]) {
  for (int col = 0; col < 1000; col++) {
    int pivot_row;
    for (int row = col; row < 1000; row++) {
      if (matrix[row][col]) {
        pivot_row = row;
        break;
      }
    }
    std::swap(matrix[col], matrix[pivot_row]);
    for (int row = col + 1; row < 1000; row++)
      if (matrix[row][col])
        matrix[row] ^= matrix[col];
  }
  for (int col = 999; col >= 0; col--)
    for (int row = col - 1; row >= 0; row--)
      if (matrix[row][col])
        matrix[row] ^= matrix[col];
}

std::string Solve(int N) {
  constexpr int W = 53;
  int m = W * 2;
  std::vector<int> a(m), b(m);
  std::vector<bool> results;
  int acc_phi = 0;

  auto matrix = std::make_unique<std::bitset<1001>[]>(1000);
  auto init_cyclic = [&](int i) -> void {
    for (int j = 0; j < i; j++) {
      a[j] = j + 1;
      a[j + i] = j + i + 1;
      b[j] = j + 1;
      b[j + i] = j + i + 1;
    }
    a[i - 1] = 0;
    a[i - 1 + i] = i;
    b[i - 1] = 0;
    b[i - 1 + i] = i;
  };
  int cur = 0;

  // Periodic vectors
  for (int i = 1; i <= W; i++) {
    init_cyclic(i);

    int phi = 0;
    for (int j = 1; j <= i; j++)
      if (std::gcd(i, j) == 1)
        phi += 1;

    for (int j = 0; j < phi; j++) {
      for (int k = 0; k < 1000; k++) {
        if (k % i == j) {
          matrix[cur][k] = 1;
        }
      }

      std::swap(b[j], b[j + i]);
      matrix[cur++][1000] = Query(m, a, b) >= i;
      std::swap(b[j], b[j + i]);
    }
  }

  { // Block 2
    auto if_0 = 2 * W - 2;
    auto if_1 = 2 * W - 1;

    for (int i = 0; i < 2 * W - 2; i++) {
      a[i] = i + 1;
      b[i] = i + 1;
    }
    a[if_0] = if_0;
    b[if_0] = if_0;
    a[if_1] = if_1;
    b[if_1] = if_1;

    for (int i = 0; i < 2 * W - 2; i++) {
      matrix[cur][i] = 1;

      a[i] = if_0;
      b[i] = if_1;
      matrix[cur++][1000] = Query(m, a, b) == if_1;
      a[i] = i + 1;
      b[i] = i + 1;
    }
  }

  // Block 3
  init_cyclic(W);
  for (int pos = 999; cur < 1000; pos--) {
    matrix[cur][pos] = 1;

    auto i = pos % W;
    std::swap(a[W + i], b[i]);
    matrix[cur++][1000] = Query(m, a, b) >= W;
    std::swap(a[W + i], b[i]);
  }

  gauss(*(std::bitset<1001>(*)[1000])matrix.get());

  std::string s;
  for (int i = 0; i < N; i++)
    s.push_back(matrix[i][1000] ? '1' : '0');

  return s;
}

Compilation message (stderr)

ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:34:7: warning: unused variable 'acc_phi' [-Wunused-variable]
   34 |   int acc_phi = 0;
      |       ^~~~~~~

• Subtask 1: 99 / 100