#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.99999) / 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;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |