Submission #1044218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044218		alex_2008	COVID tests (CEOI24_covid)	C++14	10 / 100	81 ms	424 KiB

Main

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int n, t;
long double p;
bool ch(int l, int r) {
	string s = string(n, '0');
	for (int i = l - 1; i < r; i++) {
		s[i] = '1';
	}
	cout << "Q " << s << endl;
	char x;
	cin >> x;
	if (x == 'P') return true;
	return false;
}
int main() {
	cin >> n >> p >> t;
	if (t == 1) {
		string ans = string(n, '0');
		for (int i = 1; i <= n; i++) {
			cout << "Q ";
			string s = string(n, '0');
			s[i - 1] = '1';
			cout << s << endl;
			char x;
			cin >> x;
			if (x == 'P') ans[i - 1] = '1';
		}
		cout << "A " << ans << endl;
		char x;
		cin >> x;
		return 0;
	}
	if (p <= 0.01) {
		while (t--) {
			string answ = string(n, '0');
			int last = 0;
			while (1) {
				if (!ch(last + 1, n)) {
					break;
				}
				int l = last + 1, r = n - 1, ans = last;
				while (l <= r) {
					int mid = (l + r) / 2;
					if (!ch(last + 1, mid)) {
						ans = mid;
						l = mid + 1;
					}
					else r = mid - 1;
				}
				answ[ans] = '1';
				last = ans + 1;
			}
			cout << "A " << answ << endl;
			char x;
			cin >> x;
		}
		return 0;
	}
	else {
      	int block;
      	if (p == 0.011546) block = 512;
		if (p == 0.028545) block = 256;
		if (p == 0.039856) block = 180;
		if (p == 0.068648) block = 128;
		if (p == 0.104571) block = 100;
		if (p == 0.2) block = 64;      
		while (t--) {
			string answ = string(n, '0');
			int last = 0;
			while (last < n) {
				int l = last + 1, r = min(n, last + block), ans = -1;
				while (l <= r) {
					int mid = (l + r) / 2;
					if (!ch(last + 1, mid)) {
						ans = mid;
						l = mid + 1;
					}
					else r = mid - 1;
				}
				if (ans == n) break;
				if (ans != -1) {
					answ[ans] = '1';
					last = ans + 1;
				}
				else {
					answ[last] = '1';
					last++;
				}
			}
			cout << "A " << answ << endl;
			char x;
			cin >> x;
		}
		return 0;
	}
}

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