oj.uz

Submission #1041914

# Submission time Handle Problem Language Result Execution time Memory
1041914 2024-08-02T10:14:06 Z Lucpp COVID tests (CEOI24_covid) C++17
49.09 / 100
 1591 ms 344 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 8 ms 344 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 7 ms 344 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 6 ms 344 KB Output is correct
12 Correct 6 ms 344 KB Output is correct
13 Correct 6 ms 344 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 6 ms 344 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 2 ms 344 KB Output is correct

Subtask #2
39.089999997 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 344 KB Output is correct (P=0.001, F=15.1, Q=17.1) -> 58.83 points
2 Correct 156 ms 344 KB Output is correct (P=0.005256, F=51.1, Q=67.4) -> 39.54 points
3 Correct 264 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=125.8) -> 39.09 points
4 Correct 509 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=245.7) -> 42.21 points
5 Correct 646 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=309.4) -> 44.45 points
6 Correct 918 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=437.4) -> 50.63 points
7 Correct 1093 ms 344 KB Output is correct (P=0.104571, F=490.3, Q=560.5) -> 57.23 points
8 Correct 1360 ms 344 KB Output is correct (P=0.158765, F=639.1, Q=698.1) -> 65.73 points
9 Correct 1591 ms 344 KB Output is correct (P=0.2, F=731.4, Q=779.5) -> 71.26 points