#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <math.h>
using namespace std;
void answer(vector<bool> &res) {
cout<<"A ";
for (int i = 0; i < res.size(); ++i) {
if(res[i]) cout<<"1";
else cout<<"0";
}
cout<<endl;
}
bool test(vector<int> &i,int n) {
cout<<"Q ";
vector<bool> t(n,false);
for(auto u:i) {
t[u]=true;
}
for(auto u:t) {
if(u) cout<<1;
else cout<<0;
}
cout<<endl;
char c; cin>>c;
return c=='P';
}
void check(vector<int> &n, vector<bool> &res,priority_queue<int> &free,vector<int> &k,int N) {
if(n.size()==0) return;
if(n.size()==1) {
res[n[0]]=true;
return;
}
vector<int> toTest(k[n.size()]);
for (int i = 0; i < k[n.size()]; ++i) {
toTest[i]=n[i];
}
if(test(toTest,N)) {
check(toTest,res,free,k,N);
for (int i = k[n.size()]; i < n.size(); ++i) {
free.push(n[i]);
}
}else {
vector<int> u;
for (int i = k[n.size()]; i < n.size(); ++i) {
u.push_back(n[i]);
}
for (int i = 0; i < k[n.size()]; ++i) {
res[i]=false;
}
check(u,res,free,k,N);
}
}
int main()
{
int N,T;
double p;
cin>>N>>p>>T;
int background = -1/log2(1-p);
vector<int> k(N);
for (int i = 0; i < N; ++i) {
double d =(log2(1-(1-pow(1-p,i))/2)/log2(1-p));
k[i] = d;
if(k[i]==0)k[i]=1;
}
for (int mi = 0; mi < T; ++mi) {
vector<bool> res(N);
priority_queue<int> free;
for (int i= 0; i < N; ++i) {
free.push(i);
}
while(!free.empty()) {
vector<int> o;
for (int i = 0; i < background; ++i) {
if(!free.empty()) {
o.push_back(free.top()); free.pop();
}
}
if(test(o,N)) {
check(o,res,free,k,N);
}else {
for (int i :o) {
res[i]=false;
}
}
}
answer(res);
}
}
Compilation message
Main.cpp: In function 'void answer(std::vector<bool>&)':
Main.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for (int i = 0; i < res.size(); ++i) {
| ~~^~~~~~~~~~~~
Main.cpp: In function 'void check(std::vector<int>&, std::vector<bool>&, std::priority_queue<int>&, std::vector<int>&, int)':
Main.cpp:41:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i = k[n.size()]; i < n.size(); ++i) {
| ~~^~~~~~~~~~
Main.cpp:46:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = k[n.size()]; i < n.size(); ++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
504 KB |
translate:wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
7020 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
