Submission #1147966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147966		thunopro	COVID tests (CEOI24_covid)	C++20	100 / 100	888 ms	12160 KiB

Main

// Author: Jiří Kalvoda
#include <vector>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string>
using namespace std;

bool test_pupils(vector<int>) ;

const int NMAX = 1123;
const int PMAX = 1123;

double opt_val[NMAX][PMAX];
// Expected number of queries
// indexed by: Number of students in interval; Len of prefix in which we know that someone is positive in it
int opt_ask[NMAX][PMAX];
// Optimal length of prefix to ask

double powp[NMAX]; // powp[i] = p**i

void calc(int n, double p)
{
	// dynamic programming which calculate optimal prefix to ask
	powp[0] = 1;
	for(int i=1;i<=n;i++) powp[i]=powp[i-1]*(1-p);
	opt_val[0][0] = 0;
	for(int len=1;len<=n;len++)
	{
		opt_val[len][1] = opt_val[len-1][0];
		for(int prefix=2; prefix<=len; prefix++)
		{
			opt_val[len][prefix] = NMAX;
			for(int test_len=1;test_len<prefix;test_len++)
			{
				double pr = 1-powp[test_len];
				pr /= 1-powp[prefix];
				double v = 1 +
					pr * opt_val[len][test_len] +
					(1-pr) * opt_val[len-test_len][prefix-test_len];
				if(v < opt_val[len][prefix])
				{
					opt_ask[len][prefix] = test_len;
					opt_val[len][prefix] = v;
				}
			}
		}
		opt_val[len][0] = NMAX;
		for(int test_len=1;test_len<=len;test_len++)
		{
			double pr = 1-pow(1-p, test_len);
			double v = 1 +
				pr * opt_val[len][test_len] +
				(1-pr) * opt_val[len-test_len][0];
			if(v < opt_val[len][0])
			{
				opt_ask[len][0] = test_len;
				opt_val[len][0] = v;
			}
		}
	}
}

bool calc_done;

vector<int> test(int n, double p) {
	if(!calc_done) calc(n,p);
	calc_done = true;
	vector<int> ans;
	for(int start = 0, prefix=0; start<n;)
	{
		int len = n - start;
		if(prefix == 1)
		{
			ans.push_back(start);
			prefix = 0;
			start++;
		}
		else
		{
			vector<int> ask;
			int test_len = opt_ask[len][prefix];
			for(int i=0;i<test_len;i++) ask.push_back(i+start);
			if(test_pupils(ask))
			{
				prefix = test_len;
			}
			else
			{
				if(prefix) prefix -= test_len;
				start += test_len;
			}
		}
	}
	return ans;
}

int n;
bool test_pupils(vector<int> pupils)
{
	string out(n, '0');
	for(int it : pupils)
		out[it]='1';
	fprintf(stderr, "Q %s\n", out.c_str()); fflush(stderr);
	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:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf(" %c", &in);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         scanf("%d%lf%d", &n, &p, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:127:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |                         scanf(" %c", &in);
      |                         ~~~~~^~~~~~~~~~~~

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