Submission #1207273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207273		avighna	COVID tests (CEOI24_covid)	C++20	100 / 100	507 ms	452 KiB

Main

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, t;
  double p;
  std::cin >> n >> p >> t;

  const double inf = std::numeric_limits<double>::infinity();

  std::vector<double> f(n + 2);
  std::vector<int> split(n + 2);
  for (int i = 2; i <= n + 1; ++i) {
    std::pair<double, int> opt = {inf, -1};
    double block_prob = 1 - std::pow(1 - p, i);
    for (int x = 1; x < i; ++x) {
      double p_no_a = std::pow(1 - p, x);
      double p_a = 1 - p_no_a;
      double p_b_and_no_a = p_no_a * (1 - std::pow(1 - p, i - x));
      double prob_left = p_a / block_prob;
      double prob_right = p_b_and_no_a / block_prob;
      opt = std::min(opt, {1 + prob_left * f[x] + prob_right * f[i - x], x});
    }
    f[i] = opt.first;
    split[i] = opt.second;
  }

  std::mt19937 gen(std::random_device{}());
  std::vector<int> perm(n);
  std::iota(perm.begin(), perm.end(), 0);
  std::shuffle(perm.begin(), perm.end(), gen);

  auto brute_force_method = [&]() {
    std::string ans(n, '0');
    for (int i = 0; i < n; ++i) {
      std::string q(n, '0');
      q[i] = '1';
      std::cout << "Q " << q << std::endl;
      char c;
      std::cin >> c;
      ans[i] = '0' + (c == 'P');
    }
    std::cout << "A " << ans << std::endl;
  };

  while (t--) {
    if (p < 0.001 or p > 0.2) {
      brute_force_method();
    } else {
      std::string ans(n, '0');
      for (int i = 0; i < n; ++i) {
        double p_remaining = 1 - std::pow(1 - p, n - i);
        if (p_remaining * f[n - i + 1] + 1 < f[n - i + 1]) {
          std::string q(n, '0');
          for (int j = i; j < n; ++j) {
            q[perm[j]] = '1';
          }
          std::cout << "Q " << q << std::endl;
          char c;
          std::cin >> c;
          if (c == 'N') {
            break;
          }
        }

        int l = i, r = n;
        while (l < r) {
          int m = l + split[r - l + 1] - 1;
          std::string q(n, '0');
          for (int j = l; j <= m; ++j) {
            q[perm[j]] = '1';
          }
          std::cout << "Q " << q << std::endl;
          char c;
          std::cin >> c;
          if (c == 'P') {
            r = m;
          } else {
            l = m + 1;
          }
        }
        if (l < n) {
          ans[perm[l]] = '1';
        }
        i = l;
      }
      std::cout << "A " << ans << std::endl;
    }
    char c;
    std::cin >> c;
  }
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 90 / 90