oj.uz

Submission #1060777

# Submission time Handle Problem Language Result Execution time Memory
1060777 2024-08-15T22:33:48 Z Alid COVID tests (CEOI24_covid) C++17
100 / 100
 1706 ms 14416 KB 
#include <vector>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <string>
using namespace std;

bool test_pupils(vector<int>) ;

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

int opt_ask[NMAX][PMAX]; 
double opt_val[NMAX][PMAX];
double powp[NMAX];
int permutate[NMAX];

void calc(int n, double p)
{
	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;
			}
		}
	}
	fprintf(stderr, "Except: %lf\n", opt_val[n][0]);
	fprintf(stderr, "p = %lf\n", p);
}

bool calc_done;

vector<int> test(int n, double p) {
	for(int i=0;i<n;i++) permutate[i]=i;
	srand(4);
	random_shuffle(permutate, permutate+n);
	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(permutate[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(permutate[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';
	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:109:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  scanf(" %c", &in);
      |  ~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  scanf("%d%lf%d", &n, &p, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:128:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |    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 283 ms 14160 KB Output is correct
2 Correct 273 ms 14244 KB Output is correct
3 Correct 284 ms 14416 KB Output is correct
4 Correct 274 ms 14216 KB Output is correct
5 Correct 278 ms 13996 KB Output is correct
6 Correct 286 ms 14160 KB Output is correct
7 Correct 284 ms 14160 KB Output is correct
8 Correct 286 ms 13988 KB Output is correct
9 Correct 273 ms 14160 KB Output is correct
10 Correct 285 ms 14200 KB Output is correct
11 Correct 276 ms 14160 KB Output is correct
12 Correct 278 ms 14212 KB Output is correct
13 Correct 276 ms 14416 KB Output is correct
14 Correct 274 ms 13984 KB Output is correct
15 Correct 282 ms 14160 KB Output is correct
16 Correct 272 ms 13988 KB Output is correct
17 Correct 265 ms 13988 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 14240 KB Output is correct (P=0.001, F=15.1, Q=10.8) -> 90.00 points
2 Correct 385 ms 14160 KB Output is correct (P=0.005256, F=51.1, Q=46.3) -> 90.00 points
3 Correct 468 ms 13988 KB Output is correct (P=0.011546, F=94.9, Q=90.4) -> 90.00 points
4 Correct 645 ms 14416 KB Output is correct (P=0.028545, F=191.5, Q=187.6) -> 90.00 points
5 Correct 726 ms 14160 KB Output is correct (P=0.039856, F=246.3, Q=243.6) -> 90.00 points
6 Correct 958 ms 14160 KB Output is correct (P=0.068648, F=366.2, Q=364.4) -> 90.00 points
7 Correct 1159 ms 14160 KB Output is correct (P=0.104571, F=490.3, Q=488.4) -> 90.00 points
8 Correct 1516 ms 14160 KB Output is correct (P=0.158765, F=639.1, Q=632.9) -> 90.00 points
9 Correct 1706 ms 14160 KB Output is correct (P=0.2, F=731.4, Q=729.8) -> 90.00 points