#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
using namespace std;
int n,t;
double p;
int use=0;
map<string,int>mp;
int ask(string v){
if(mp[v]!=0)return mp[v]-1;
//use++;
cout<<"Q ";
cout<<v;
cout<<endl;
//cerr<<"input:"<<endl;
char ans;
cin>>ans;
//cerr<<ans<<endl;
return (mp[v]=(ans=='P'?1:0)+1)-1;
}
int ask(int st,int en){
en=min(n-1,en);
string temp(n,'0');
for(int i=st;i<=en;i++)temp[i]='1';
return ask(temp);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>p>>t;
int freq=n/(p*n);
int mx=0;
while((1<<mx)<freq)mx++;
mx--;
mx=min(9,mx);
mx=max(0,mx);
while(t--){
//cerr<<"work"<<endl;
mp.clear();
int cur=-1;
string ans=string(n,'0');
int og=cur;
while(cur<n-1){
int nmx=0;
if(cur+(1<<mx)>=n){
while(cur+(1<<nmx)<n)nmx++;
nmx--;
}else{
nmx=mx;
}
//cout<<nmx<<endl;
if(ask(og+1,cur+(1<<nmx))){
for(int i=nmx-1;i>=0;i--)if(!ask(og+1,cur+(1<<i)))cur=cur+(1<<i);
cur++;
ans[cur]='1';
og=cur;
}else{
cur=cur+(1<<nmx);
continue;
//cout<<"overflow"<<endl;
int nw=nmx+1;
while(cur+(1<<nw)<n&&ask(cur+1,cur+(1<<nw))==0){
nw++;
}
//cout<<"end"<<nw<<endl;
if(cur+(1<<nw)>=n){
//cout<<"still ov"<<cur<<" "<<n<<endl;
if(!ask(cur+1,n-1))break;
//cout<<"what"<<endl;
int ogcur=cur;
for(int i=nw-1;i>=0;i--)if(!ask(ogcur+1,cur+(1<<i)))cur=cur+(1<<i);
cur++;
ans[cur]='1';
}else{
//cout<<"not ov"<<endl;
int ogcur=cur;
for(int i=nw-1;i>=0;i--)if(!ask(ogcur+1,cur+(1<<i)))cur=cur+(1<<i);
cur++;
ans[cur]='1';
}
}
}
//cout<<x<<endl;
//cout<<ask(x)<<endl;
//assert(ask(x)==0);
cout<<"A ";
cout<<ans;
cout<<endl;
char res;
cin>>res;
//cerr<<"use:"<<use<<endl;
if(res=='W')break;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1484 KB |
Output is correct |
2 |
Correct |
5 ms |
1364 KB |
Output is correct |
3 |
Correct |
6 ms |
1368 KB |
Output is correct |
4 |
Correct |
7 ms |
1444 KB |
Output is correct |
5 |
Correct |
6 ms |
1480 KB |
Output is correct |
6 |
Correct |
6 ms |
1556 KB |
Output is correct |
7 |
Correct |
6 ms |
1412 KB |
Output is correct |
8 |
Correct |
5 ms |
1324 KB |
Output is correct |
9 |
Correct |
5 ms |
1368 KB |
Output is correct |
10 |
Correct |
4 ms |
1012 KB |
Output is correct |
11 |
Correct |
7 ms |
1420 KB |
Output is correct |
12 |
Correct |
7 ms |
1368 KB |
Output is correct |
13 |
Correct |
6 ms |
1448 KB |
Output is correct |
14 |
Correct |
5 ms |
1368 KB |
Output is correct |
15 |
Correct |
7 ms |
1436 KB |
Output is correct |
16 |
Correct |
5 ms |
1624 KB |
Output is correct |
17 |
Correct |
6 ms |
1296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
508 KB |
Output is correct (P=0.001, F=15.1, Q=14.2) -> 90.00 points |
2 |
Correct |
93 ms |
344 KB |
Output is correct (P=0.005256, F=51.1, Q=48.6) -> 90.00 points |
3 |
Correct |
160 ms |
848 KB |
Output is correct (P=0.011546, F=94.9, Q=92.5) -> 90.00 points |
4 |
Correct |
340 ms |
1360 KB |
Output is correct (P=0.028545, F=191.5, Q=190.4) -> 90.00 points |
5 |
Correct |
452 ms |
1228 KB |
Output is correct (P=0.039856, F=246.3, Q=244.8) -> 90.00 points |
6 |
Correct |
666 ms |
1380 KB |
Output is correct (P=0.068648, F=366.2, Q=366.2) -> 90.00 points |
7 |
Correct |
863 ms |
1844 KB |
Output is correct (P=0.104571, F=490.3, Q=493.7) -> 87.57 points |
8 |
Correct |
1139 ms |
1676 KB |
Output is correct (P=0.158765, F=639.1, Q=633.2) -> 90.00 points |
9 |
Correct |
1380 ms |
1544 KB |
Output is correct (P=0.2, F=731.4, Q=740.9) -> 85.55 points |