제출 #1206601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206601		avighna	COVID tests (CEOI24_covid)	C++20	58.92 / 100	540 ms	436 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;

  std::mt19937 gen(std::random_device{}());
  auto probabilistic_method = [&]() {
    std::vector<int> a(n);
    std::iota(a.begin(), a.end(), 0);
    std::shuffle(a.begin(), a.end(), gen);
    std::string ans(n, '0');
    std::vector<int> idx;
    auto solve_dnc = [&](auto &&self, int l, int r, bool left_zero) {
      if (l == r and left_zero) {
        ans[idx[l]] = '1';
        return true;
      }
      char c;
      if (left_zero) {
        c = 'P';
      } else {
        std::string q(n, '0');
        for (int i = l; i <= r; ++i) {
          q[idx[i]] = '1';
        }
        std::cout << "Q " << q << std::endl;
        std::cin >> c;
      }
      if (c == 'N') {
        return false;
      }
      if (l == r) {
        ans[idx[l]] = '0' + (c == 'P');
        return c == 'P';
      }
      int m = (l + r) / 2;
      bool b = self(self, l, m, false);
      self(self, m + 1, r, !b);
      return true;
    };
    int group_size = std::round(std::log(0.64) / std::log(1 - p));
    while (!a.empty()) {
      for (int i = 0; i < group_size and !a.empty(); ++i) {
        idx.push_back(a.back());
        a.pop_back();
      }
      solve_dnc(solve_dnc, 0, idx.size() - 1, false);
      idx.clear();
    }
    std::cout << "A " << ans << std::endl;
  };

  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;
  };

  auto binary_search_method = [&]() {
    std::string ans(n, '0');
    for (int i = 0; i < n; ++i) {
      int s = i, e = n;
      while (s < e) {
        int m = (s + e) / 2;
        std::string q(n, '0');
        for (int idx = i; idx <= m; ++idx) {
          q[idx] = '1';
        }
        std::cout << "Q " << q << std::endl;
        char c;
        std::cin >> c;
        if (c == 'P') {
          e = m;
        } else {
          s = m + 1;
        }
      }
      if (s < n) {
        ans[s] = '1';
      }
      i = s;
    }
    std::cout << "A " << ans << std::endl;
  };

  while (t--) {
    if (p < 0.001 or p > 0.2) {
      brute_force_method();
    } else if (p > 0.005 and p < 0.02) {
      binary_search_method();
    } else {
      probabilistic_method();
    }
    char c;
    std::cin >> c;
  }
}

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