#include <bits/stdc++.h>
/*
Bernoulli process; attempt to split set into half every query
*/
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n,t;
double p;
std::cin>>n>>p>>t;
std::vector<double> bsvals;
for(int i=0;i<=n;i++){
bsvals.push_back(pow(1-p,i));
}
while(t--){
int ind=0;
std::vector<int> sol(n);
while(ind<n){
int lnum=0,unum=n-ind+1;//number of 0s before 1 or end
while(lnum+1<unum){
double midprob=-(bsvals[unum]+bsvals[lnum])/2;//prob there are no more cases
int lhnum=lnum+1,uhnum=unum;
while(lhnum+1<uhnum){
int mnum=(lhnum+uhnum)/2;
double mprob=-bsvals[mnum];
if(mprob<midprob){
lhnum=mnum;
}else{
uhnum=mnum;
}
}
int qnum;
if(std::abs(-bsvals[uhnum]-midprob)<std::abs(-bsvals[lhnum]-midprob)){
qnum=uhnum;
}else{
qnum=lhnum;
}
std::string mstr(n,'0');
std::cout<<"Q ";
for(int i=ind;i<ind+qnum;i++){
mstr[i]='1';
}
std::cout<<mstr;
std::cout<<'\n';
std::cout.flush();
char c;
std::cin>>c;
if(c=='N'){
lnum=qnum;
}else{
unum=qnum;
}
}
ind+=lnum;
sol[ind]=1;
ind++;
}
std::cout<<"A ";
std::string mstr(n,'0');
for(int i=0;i<n;i++){
mstr[i]='0'+sol[i];
}
std::cout<<mstr<<'\n';
std::cout.flush();
char c;
std::cin>>c;
if(c=='W')return 0;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
344 KB |
Output is correct |
2 |
Correct |
6 ms |
344 KB |
Output is correct |
3 |
Correct |
5 ms |
344 KB |
Output is correct |
4 |
Correct |
3 ms |
344 KB |
Output is correct |
5 |
Correct |
4 ms |
344 KB |
Output is correct |
6 |
Correct |
4 ms |
344 KB |
Output is correct |
7 |
Correct |
4 ms |
344 KB |
Output is correct |
8 |
Correct |
4 ms |
344 KB |
Output is correct |
9 |
Correct |
3 ms |
344 KB |
Output is correct |
10 |
Correct |
2 ms |
344 KB |
Output is correct |
11 |
Correct |
3 ms |
344 KB |
Output is correct |
12 |
Correct |
5 ms |
344 KB |
Output is correct |
13 |
Correct |
4 ms |
344 KB |
Output is correct |
14 |
Correct |
4 ms |
344 KB |
Output is correct |
15 |
Correct |
4 ms |
344 KB |
Output is correct |
16 |
Correct |
4 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
344 KB |
Output is correct (P=0.001, F=15.1, Q=15.1) -> 90.00 points |
2 |
Correct |
88 ms |
344 KB |
Output is correct (P=0.005256, F=51.1, Q=52.0) -> 84.08 points |
3 |
Correct |
169 ms |
344 KB |
Output is correct (P=0.011546, F=94.9, Q=95.2) -> 88.88 points |
4 |
Correct |
341 ms |
344 KB |
Output is correct (P=0.028545, F=191.5, Q=190.9) -> 90.00 points |
5 |
Correct |
452 ms |
344 KB |
Output is correct (P=0.039856, F=246.3, Q=247.5) -> 88.28 points |
6 |
Correct |
646 ms |
344 KB |
Output is correct (P=0.068648, F=366.2, Q=366.8) -> 89.41 points |
7 |
Correct |
879 ms |
344 KB |
Output is correct (P=0.104571, F=490.3, Q=492.9) -> 88.13 points |
8 |
Correct |
1135 ms |
344 KB |
Output is correct (P=0.158765, F=639.1, Q=633.7) -> 90.00 points |
9 |
Correct |
1241 ms |
344 KB |
Output is correct (P=0.2, F=731.4, Q=729.7) -> 90.00 points |