QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#499712#9162. COVID testskshitij_sodani#0 58ms3796kbC++171.9kb2024-07-31 17:36:362024-07-31 17:36:36

Judging History

你现在查看的是最新测评结果

  • [2024-07-31 17:36:36]
  • 评测
  • 测评结果:0
  • 用时:58ms
  • 内存:3796kb
  • [2024-07-31 17:36:36]
  • 提交

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