Submission #1052269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052269		n1k	COVID tests (CEOI24_covid)	C++17	70.28 / 100	1238 ms	2896 KiB

Main

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

bool test_pupils(vector<int>) ;

const int NMAX = 112345;

int opt_ask[NMAX][2]; // Počet lidí; Zda víme existenci alespoň jednoho pozitivního
double opt_val[NMAX][2];

void f(vector<int> & out, int start, int len, bool exist)
{
	//fprintf(stderr, "start: %d len: %d exist: %d\n", start, len, exist);
	if(len < 1) return;
	if(len == 1 && exist)
	{
		out.push_back(start);
		return;
	}
	vector<int> ask;
	int test_len = opt_ask[len][exist];
	for(int i=0;i<test_len;i++) ask.push_back(i+start);
	//fprintf(stderr,"test_len: %d\n", test_len);
	if(test_pupils(ask))
	{
		f(out, start, test_len, 1);
		f(out, start+test_len, len-test_len, 0);
	}
	else
		f(out, start+test_len, len-test_len, exist);
}

vector<int> test(int n, double p) {
	//for(int len=0;len<=n;len++) fprintf(stderr, "%lf->%d %lf->%d\n", opt_val[len][0], opt_ask[len][0],  opt_val[len][1], opt_ask[len][1]);
	fprintf(stderr, "Except: %lf\n", opt_val[n][0]);
	fprintf(stderr, "p = %lf\n", p);
	vector<int> ans;
	f(ans, 0, n, 0);
	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);


	opt_val[0][0] = opt_val[0][1] = 0;
	opt_val[1][0] = 1;
	opt_val[1][1] = 0;

	opt_ask[1][0] = 1;
	opt_ask[1][1] = 1;
	for(int len=2;len<=n;len++)
	for(int exist=2; exist-->0;)
	{
		opt_val[len][exist] = NMAX;
		for(int test_len=1;test_len<=(len-exist);test_len++)
		{
			double pr = 1-pow(1-p, test_len);
			if(exist)
			{
				pr /= 1-pow(1-p, len);
			}
			double v = 1 +
				pr * (opt_val[test_len][1] + opt_val[len-test_len][0]) +
				(1-pr) * opt_val[len-test_len][exist];
			if(v < opt_val[len][exist])
			{
				opt_ask[len][exist] = test_len;
				opt_val[len][exist] = v;
			}
		}
	}
	//cerr << opt_val[2][0] << endl;


	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:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf(" %c", &in);
      |  ~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d%lf%d", &n, &p, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:109:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |    scanf(" %c", &in);
      |    ~~~~~^~~~~~~~~~~~

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