oj.uz

Submission #1025968

# Submission time Handle Problem Language Result Execution time Memory
1025968 2024-07-17T11:58:33 Z model_code COVID tests (CEOI24_covid) C++17
100 / 100
 2587 ms 234700 KB 
// 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

Main.cpp: In function 'bool test_pupils(std::vector<int>)':
Main.cpp:108:7: 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:7: 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:9: 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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 14980 KB Output is correct
2 Correct 300 ms 14928 KB Output is correct
3 Correct 294 ms 14928 KB Output is correct
4 Correct 301 ms 14416 KB Output is correct
5 Correct 295 ms 14980 KB Output is correct
6 Correct 296 ms 15184 KB Output is correct
7 Correct 287 ms 14928 KB Output is correct
8 Correct 308 ms 14716 KB Output is correct
9 Correct 317 ms 14924 KB Output is correct
10 Correct 300 ms 14224 KB Output is correct
11 Correct 289 ms 15040 KB Output is correct
12 Correct 297 ms 14928 KB Output is correct
13 Correct 312 ms 14924 KB Output is correct
14 Correct 283 ms 14928 KB Output is correct
15 Correct 292 ms 14592 KB Output is correct
16 Correct 277 ms 14928 KB Output is correct
17 Correct 282 ms 14128 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 16924 KB Output is correct (P=0.001, F=15.1, Q=10.8) -> 90.00 points
2 Correct 447 ms 27768 KB Output is correct (P=0.005256, F=51.1, Q=46.3) -> 90.00 points
3 Correct 592 ms 41408 KB Output is correct (P=0.011546, F=94.9, Q=90.5) -> 90.00 points
4 Correct 874 ms 71444 KB Output is correct (P=0.028545, F=191.5, Q=187.7) -> 90.00 points
5 Correct 1026 ms 88388 KB Output is correct (P=0.039856, F=246.3, Q=243.7) -> 90.00 points
6 Correct 1340 ms 124296 KB Output is correct (P=0.068648, F=366.2, Q=364.2) -> 90.00 points
7 Correct 1690 ms 161396 KB Output is correct (P=0.104571, F=490.3, Q=488.2) -> 90.00 points
8 Correct 2334 ms 205028 KB Output is correct (P=0.158765, F=639.1, Q=633.1) -> 90.00 points
9 Correct 2587 ms 234700 KB Output is correct (P=0.2, F=731.4, Q=729.3) -> 90.00 points