Submission #1178485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178485		avighna	Magic Show (APIO24_show)	C++20	0 / 100	4 ms	356 KiB

Alice

#include "Alice.h"
#include <random>
#include <vector>

std::vector<std::pair<int, int>> Alice() {
  const int seed = 69;
  const int bits = 20;
  const int n = 5000;

  long long x = setN(n);
  std::mt19937 rng(seed);
  std::uniform_int_distribution<int> dist(0, 1);

  std::vector<std::pair<int, int>> adj;
  adj.push_back({1, 2});
  for (int i = 0; i < n - 2; ++i) {
    int sum = 0;
    for (int j = 0; j < bits; ++j) {
      sum += !!(x & (1LL << j)) * dist(rng);
    }
    if (sum & 1) {
      adj.push_back({1, i + 3});
    } else {
      adj.push_back({2, i + 3});
    }
  }

  return adj;
}

Bob

#include "Bob.h"
#include <cassert>
#include <random>
#include <vector>

long long Bob(std::vector<std::pair<int, int>> V) {
  const int seed = 69;
  const int bits = 20;
  const int n = 5000;

  std::mt19937 rng(seed);
  std::uniform_int_distribution<int> dist(0, 1);

  std::vector<long long> a(n - 2);
  for (int i = 0; i < n - 2; ++i) {
    for (int j = 0; j < bits; ++j) {
      a[i] += (1LL << j) * dist(rng);
    }
  }
  std::vector<bool> good(n - 2);
  for (auto &[u, v] : V) {
    if (u == 1 and v == 2) {
      continue;
    }
    a[v - 3] += (1LL << bits) * (u % 2);
    good[v - 3] = true;
  }
  for (int i = 0; i < n - 2; ++i) {
    if (!good[i]) {
      a[i] = 0;
    }
  }

  long long x = 0;
  // i ==> eq number, j ==> var number
  auto solve = [&](auto &&self, int i, int j) {
    if (i >= a.size()) {
      return;
    }
    if (!(a[i] & (1LL << j))) {
      for (int k = i + 1; k < a.size(); ++k) {
        if (a[k] & (1LL << j)) {
          std::swap(a[i], a[k]);
          break;
        }
      }
    }
    if (!(a[i] & (1LL << j))) {
      return;
    }
    for (int k = i + 1; k < a.size(); ++k) {
      if (a[k] & (1LL << j)) {
        a[k] ^= a[i];
      }
    }
    if (j == bits - 1) {
      x += (1LL << j) * !!(a[i] & (1LL << bits));
      return;
    }
    self(self, i + 1, j + 1);
    int ans = !!(a[i] & (1LL << bits));
    for (int k = j + 1; k < bits; ++k) {
      if (a[i] & (1LL << k)) {
        ans -= !!(x & (1LL << k));
      }
    }
    ans = (ans % 2 + 2) % 2;
    x += (1LL << j) * ans;
  };
  solve(solve, 0, 0);

  return x;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65