제출 #1207206

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207206		avighna	COVID tests (CEOI24_covid)	C++20	47.35 / 100	517 ms	444 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) {
    double best = inf;
    int best_x = -1;
    double block_pos_prob = 1 - std::pow(1 - p, i);
    for (int x = 1; x < i; ++x) {
      double p_a = 1 - std::pow(1 - p, x);
      double p_no_a = std::pow(1 - p, x);
      double p_band_no_a = p_no_a * (1 - std::pow(1 - p, i - x));
      double prob_left = p_a / block_pos_prob;
      double prob_right = p_band_no_a / block_pos_prob;
      double cur = 1 + prob_left * f[x] + prob_right * f[i - x];
      if (cur < best) {
        best = cur;
        best_x = x;
      }
    }

    f[i] = best;
    split[i] = best_x;
  }

  while (t--) {
    std::string ans(n, '0');
    for (int i = 0; i < n; ++i) {
      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[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[l] = '1';
      }
      i = l;
    }
    std::cout << "A " << ans << std::endl;
    char c;
    std::cin >> c;
  }
}

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