Submission #1220147

#TimeUsernameProblemLanguageResultExecution timeMemory
1220147MateiKing80COVID tests (CEOI24_covid)C++20
89.83 / 100
782 ms408 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
#define fr first
#define sc second

int n;
double p;

bool test_students(vector<bool> mask) {
	string str(n, ' ');
	for (int i = 0; i < n; i ++)
		str[i] = mask[i] ? '1' : '0';
	cout << "Q " << str << endl;
	char ans;
	cin >> ans;
	return ans == 'P';
}

bool range_query(int l, int r, vector<bool> &query) {
	if (r <= l) 
		return 0;
	r = min(r, n);
	for (int i = l; i < r; i ++)
		query[i] = 1;
	bool res = test_students(query);
	for (int i = l; i < r; i ++)
		query[i] = 0;
	return res;
}

vector<bool> find_positive() {
	vector<bool> ans(n, 0), query(n, 0);
	int l = 0;
	while (l < n) {
		int x = ((p == 0) ? n : (1 / p));
		int r = min(l + x, n);
		bool val = range_query(l, r, query);
		  
		if (val == 0) {
			l = r;
			continue;
		}
		int lo = l;
		int hi = r;
		while (hi - lo > 1) {
			int mid = (lo + hi) / 2;
			if (range_query(l, mid, query))
				hi = mid;
			else
				lo = mid;
		}
		ans[lo] = 1;
		l = hi;
	}
	return ans;
}

int main() {
	int T;
	cin >> n >> p >> T;
	for (int i = 0; i < T; i ++) {
		vector<bool> ans = find_positive();
		string str(n, ' ');
		for (int j = 0; j < n; j++)
			str[j] = ans[j] ? '1' : '0';

		cout << "A " << str << endl;
		char ch;
		cin >> ch;
		if (ch == 'W')
			exit(0);
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...