Submission #1178140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178140		avighna	Magic Show (APIO24_show)	C++20	0 / 100	9 ms	616 KiB

Alice

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

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

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

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

Bob

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

void gauss(std::vector<std::bitset<61>> a, int n, int m,
           std::vector<bool> &ans) {
  std::vector<int> where(m, -1);
  for (int col = 0, row = 0; col < m && row < n; ++col) {
    for (int i = row; i < n; ++i)
      if (a[i][col]) {
        swap(a[i], a[row]);
        break;
      }
    if (!a[row][col])
      continue;
    where[col] = row;

    for (int i = 0; i < n; ++i)
      if (i != row && a[i][col])
        a[i] ^= a[row];
    ++row;
  }
  for (int j = 0; j < m; ++j) {
    if (where[j] != -1) {
      ans[j] = a[where[j]][m];
    }
  }
}

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

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

  std::vector<std::bitset<61>> a(n - 2);
  for (int i = 0; i < n - 2; ++i) {
    for (int j = 0; j < 60; ++j) {
      a[i][j] = dist(rng);
    }
  }
  std::vector<bool> good(n - 2);
  for (auto &[u, v] : V) {
    a[v - 3][60] = u % 2;
    good[v - 3] = true;
  }
  for (int i = 0; i < n - 2; ++i) {
    if (!good[i]) {
      for (int j = 0; j < 60; ++j) {
        a[i][j] = 0;
      }
    }
  }

  std::vector<bool> ans(60);
  gauss(a, n - 2, 60, ans);
  long long x = 0;
  for (int bt = 0; bt < 60; ++bt) {
    x += ans[bt] * (1LL << bt);
  }
  return x;
}

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