QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#499712 | #9162. COVID tests | kshitij_sodani# | 0 | 58ms | 3796kb | C++17 | 1.9kb | 2024-07-31 17:36:36 | 2024-07-31 17:36:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
pair<long double,llo> dp[1001];
long double pre[1001];
int n,t;
mt19937 rng;
int ans[1001];
int query(vector<int> xx){
vector<int> yy;
for(int i=0;i<n;i++){
yy.pb(0);
}
for(auto j:xx){
yy[j]=1;
}
cout<<"Q ";
for(auto j:yy){
cout<<j;
}
cout<<endl;
char s;
cin>>s;
if(s=='P'){
return 1;
}
return 0;
}
void solve(int l,int r,vector<int> yy){
if(l==r){
if(query(yy)==1){
ans[yy[0]]=1;
}
return;
}
rng=mt19937(chrono::steady_clock::now().time_since_epoch().count());
int x=dp[r-l+1].b;
shuffle(yy.begin(),yy.end(),rng);
int ok=0;
//cout<<r-l+1<<":::"<<x<<endl;
for(int j=l;j<=r;j+=1){
int k=min(j+x-1,r);
k=j;
vector<int> xx;
for(int ii=j;ii<=k;ii++){
xx.pb(yy[ii-l]);
}
/*if(l>0 or r<n-1){
if(k==r and ok==0){
if(j==k){
ans[j]=1;
}
else{
solve(j,k,xx);
}
continue;
}
}*/
if(query(xx)==1){
ok=1;
if(j==k){
ans[j]=1;
}
else{
solve(j,k,xx);
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long double p;
cin>>n>>p>>t;
pre[0]=1;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]*(1-p);
}
dp[1]={0,-1};
for(int i=2;i<=n;i++){
dp[i]={i,1};
for(int j=1;j<=i-1;j++){
pair<llo,llo> cur={(i+j-1)/j,j};
llo xx=1-pre[j];
cur.a+=xx*(i/j);
if(i%j!=0){
llo xx=(1-pre[i%j]);
cur.a+=xx;
}
if(cur.a<dp[i].a-0.0001){
dp[i]=cur;
}
}
}
while(t--){
for(int i=0;i<n;i++){
ans[i]=0;
}
vector<int> zz;
for(int i=0;i<n;i++){
zz.pb(i);
}
solve(0,n-1,zz);
cout<<"A ";
for(int i=0;i<n;i++){
cout<<ans[i];
}
cout<<endl;
char z;
cin>>z;
if(z=='C'){
continue;
}
return 0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 31ms
memory: 3792kb
input:
1000 0.789673 1 N P P P P P P N P P P P P P P N P P P P P P P P P P P P P N P P P N P N P P P P N P P P N N P P P P N P P P P N P P P P N P P P P P P P P P P P P P P P P N P P P P P P P P P P N P P P P P P N P N P P P P P N P P P P P N P P P P P N N P N N N P P N P P P N P P P P P P P P N P P N P N ...
output:
Q 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000...
result:
points 0.0 0.0 translate:wrong
Subtask #2:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 58ms
memory: 3796kb
input:
1000 0.001 300 N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N...
output:
Q 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 0.0 0.0 translate:wrong