Submission #1044319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044319		alex_2008	COVID tests (CEOI24_covid)	C++14	59.26 / 100	1177 ms	596 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;
string p;
bool ch(int l, int r) {
	if (l > r) return false;
	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;
	}
	int block;
	if (p == "0.001" || p == "0.005256") block = 1000;
	if (p == "0.005256") block = 255;
	if (p == "0.011546") block = 255;
	if (p == "0.028545") block = 127;
	if (p == "0.039856") block = 127;
	if (p == "0.068648") block = 63;
	if (p == "0.104571") block = 31;
	if (p == "0.158765") block = 5;
	if (p == "0.2") block = 3;
	while (t--) {
		string answ = string(n, '0');
		for (int i = 1; i <= n; i += block) {
			int mx_r = min(n, i + block - 1);
			int last = i - 1;
			while (1) {
				if (!ch(last + 1, mx_r)) {
					break;
				}
				int l = last + 1, r = mx_r - 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;
}

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