Submission #1041914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041914		Lucpp	COVID tests (CEOI24_covid)	C++17	49.09 / 100	1591 ms	344 KiB

Main

#include <bits/stdc++.h>
using namespace std;
constexpr double inf = 1e9;

int N;
double P;

string toStr(vector<bool> mask){
	string str(N, ' ');
	for (int i = 0; i < N; i++)
		str[i] = "01"[mask[i]];
	return str;
}

// int qryCnt = 0;
// vector<bool> solution;

bool query(vector<bool> mask) {
	cout << "Q " << toStr(mask) << endl;
	char ans;
	cin >> ans;
	return ans == 'P';
	// qryCnt++;
	// for(int i = 0; i < N; i++){
	// 	if(solution[i] && mask[i]) return true;
	// }
	// return false;
}

bool queryInterval(int l, int r){
	vector<bool> mask(N);
	for(int i = l; i < r; i++) mask[i] = true;
	return query(mask);
}

vector<double> dp0, dp1;
vector<int> strat0, strat1;

void rec(vector<bool>& ans, int i, int k, bool has1){
	if(k == 0) return;
	if(k == 1 && has1){
		ans[i] = true;
		return;
	}
	if(!has1){
		int j = strat0[k];
		if(queryInterval(i, i+j)){
			rec(ans, i, j, true);
		}
		rec(ans, i+j, k-j, false);
	}
	else{
		int j = strat1[k];
		if(queryInterval(i, i+j)){
			rec(ans, i, j, true);
			rec(ans, i+j, k-j, false);
		}
		else{
			rec(ans, i+j, k-j, true);
		}
	}
}

vector<bool> solve() {
	vector<bool> ans(N);
	rec(ans, 0, N, false);
	return ans;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	int T;
	cin >> N >> P >> T;
	dp0.assign(N+1, inf), dp1.assign(N+1, inf);
	strat0.assign(N+1, -1), strat1.assign(N+1, -1);
	dp0[0] = dp1[0] = dp1[1] = 0;
	dp0[1] = 1;
	strat0[1] = 1;
	vector<double> p0(N+1);
	p0[0] = 1;
	for(int i = 1; i <= N; i++) p0[i] = p0[i-1] * (1.0 - P);
	for(int i = 2; i <= N; i++){
		for(int j = 1; j < i; j++){
			double ex = 1.0 + p0[j] * dp0[i-j] + (1.0 - p0[j]) * (dp1[j] + dp0[i-j]);
			if(ex < dp0[i]){
				dp0[i] = ex;
				strat0[i] = j;
			}
		}
		for(int j = 1; j < i; j++){
			double myP = p0[j] * (1.0 - p0[i-j]) / (1.0 - p0[i]);
			double ex = 1.0 + myP * dp1[i-j] + (1.0 - myP) * (dp1[j] + dp0[i-j]);
			if(ex < dp1[i]){
				dp1[i] = ex;
				strat1[i] = j;
			}
		}
	}
	// cerr << dp0[N] << "\n";
	for(int i = 0; i < T; i++) {
		// solution.resize(N);
		// for(int j = 0; j < N; j++){
		// 	solution[j] = ((double)rand() / RAND_MAX) < P;
		// }
		vector<bool> ans = solve();
		// if(ans != solution){
		// 	cout << "WA\n";
		// 	break;
		// }
		cout << "A " << toStr(ans) << endl;
		char verdict;
		cin >> verdict;
		if (verdict == 'W')
			return 0;
	}
	// cerr << ((double)qryCnt / T) << "\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 39.089999997 / 90