Submission #1025971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025971		model_code	COVID tests (CEOI24_covid)	C++17	41.44 / 100	1765 ms	600 KiB

Main

// Solution which just knary searches.
// I imagine it should receive around 4 pts.
// Author: Ondra Sladký
#include <vector>
#include <queue>
#include <cassert>
#include <string>
using namespace std;


bool test_pupils(vector<int>) ;

vector<int> test(int n, double p) {
	// Do the queries.
	vector<int> ans;
	queue<pair<int, int>> q;
	q.emplace(0, n);
	while(!q.empty()) {
		auto front = q.front();
		int from = front.first;
		int to = front.second;
		q.pop();
		if (to == from) continue;
		vector<int> tested;
		for(int i = from; i < to; ++i) tested.push_back(i);
		int sz = tested.size();
		if (!test_pupils(tested)) continue;
		if (sz == 1) {
			ans.push_back(from);
			continue;
		}
		int k = 4;
		assert(k!=-1);
		int smaller_size = sz / k;
		int higher_size = smaller_size + 1;
		int higher_count = sz % k;
		int smaller_count = k - higher_count;

		for (int i = 0, last = from; i < k; ++i) {
			int dif = higher_size;
			if (i < smaller_count) dif = smaller_size;
			int next = last + dif;
			q.emplace(last, next);
			last = next;
		}
	}
	return ans;
}


int n;
bool test_pupils(vector<int> pupils)
{
	string out(n, '0');
	for(int it : pupils)
		out[it]='1';
	printf("Q %s\n", out.c_str());
	fflush(stdout);
	char in;
	scanf(" %c", &in);
	return in=='P';
}

int main()
{
	double p;
	int t;
	scanf("%d%lf%d", &n, &p, &t);
	for(int ti=0; ti<t; ti++)
	{
		auto positive = test(n, p);
		{
			string out(n, '0');
			for(int it : positive)
				out[it]='1';
			printf("A %s\n", out.c_str());
			fflush(stdout);
			char in;
			scanf(" %c", &in);
			if(in != 'C') return 0;
		}
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'bool test_pupils(std::vector<int>)':
Main.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf(" %c", &in);
      |  ~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d%lf%d", &n, &p, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |    scanf(" %c", &in);
      |    ~~~~~^~~~~~~~~~~~

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