Submission #1206462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206462		avighna	COVID tests (CEOI24_covid)	C++20	10 / 100	33 ms	412 KiB

Main

#include <bits/stdc++.h>

int main() {
  int n, t;
  double p;
  std::cin >> n >> p >> t;

  if (t == 1) {
    std::vector<bool> ans(n);
    for (int i = 0; i < n; ++i) {
      std::cout << "Q ";
      for (int j = 0; j < n; ++j) {
        std::cout << (i == j);
      }
      std::cout << std::endl;
      char c;
      std::cin >> c;
      ans[i] = c == 'P';
    }
    std::cout << "A ";
    for (int i = 0; i < n; ++i) {
      std::cout << ans[i];
    }
    std::cout << std::endl;
    char c;
    std::cin >> c;
    return 0;
  }

  std::mt19937 gen(std::random_device{}());
  int log = std::log(0.5) / std::log(1 - p);
  while (t--) {
    std::vector<int> rem(n);
    std::iota(rem.begin(), rem.end(), 0);
    std::vector<bool> ans(n);
    int cnt = 0;
    while (!rem.empty()) {
      int sample_size = std::max(1, std::min(int(rem.size()) >> (cnt + 1), log));
      std::shuffle(rem.begin(), rem.end(), gen);
      std::vector<bool> q(n);
      int last = -1;
      for (int i = 0; i < sample_size and !rem.empty(); ++i) {
        q[last = rem.back()] = true;
        rem.pop_back();
      }
      if (last == -1) {
        break;
      }
      std::cout << "Q ";
      for (int i = 0; i < n; ++i) {
        std::cout << q[i];
      }
      std::cout << std::endl;
      char c;
      std::cin >> c;
      if (sample_size == 1) {
        ans[last] = c == 'P';
      }
      if (c == 'P') {
        if (sample_size > 1) {
          for (int i = 0; i < n; ++i) {
            if (q[i]) {
              rem.push_back(i);
            }
          }
        }
        cnt++;
      } else {
        cnt = 0;
      }
      int max_cnt = std::log(1 - 0.999) / std::log(1 - std::pow(1 - p, sample_size));
      if (cnt > max_cnt) {
        break;
      }
    }
    while (!rem.empty()) {
      ans[rem.back()] = true;
      rem.pop_back();
    }

    std::cout << "A ";
    for (int i = 0; i < n; ++i) {
      std::cout << ans[i];
    }
    std::cout << std::endl;
    char c;
    std::cin >> c;
    if (c == 'W') {
      return 0;
    }
  }
}

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