oj.uz

Submission #1052269

# Submission time Handle Problem Language Result Execution time Memory
1052269 2024-08-10T12:54:13 Z n1k COVID tests (CEOI24_covid) C++17
70.28 / 100
 1238 ms 2896 KB 
// 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

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 / 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 41 ms 2620 KB Output is correct
2 Correct 37 ms 2492 KB Output is correct
3 Correct 42 ms 2896 KB Output is correct
4 Correct 36 ms 2896 KB Output is correct
5 Correct 42 ms 2640 KB Output is correct
6 Correct 43 ms 2524 KB Output is correct
7 Correct 27 ms 2896 KB Output is correct
8 Correct 24 ms 2640 KB Output is correct
9 Correct 31 ms 2624 KB Output is correct
10 Correct 23 ms 2392 KB Output is correct
11 Correct 29 ms 2392 KB Output is correct
12 Correct 25 ms 2640 KB Output is correct
13 Correct 25 ms 2640 KB Output is correct
14 Correct 26 ms 2648 KB Output is correct
15 Correct 25 ms 2532 KB Output is correct
16 Correct 11 ms 2644 KB Output is correct
17 Correct 15 ms 2388 KB Output is correct

Subtask #2
60.280000002 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2640 KB Output is correct (P=0.001, F=15.1, Q=13.2) -> 90.00 points
2 Correct 101 ms 2524 KB Output is correct (P=0.005256, F=51.1, Q=55.9) -> 65.42 points
3 Correct 199 ms 2648 KB Output is correct (P=0.011546, F=94.9, Q=106.6) -> 60.28 points
4 Correct 370 ms 2764 KB Output is correct (P=0.028545, F=191.5, Q=214.2) -> 61.05 points
5 Correct 456 ms 2512 KB Output is correct (P=0.039856, F=246.3, Q=273.3) -> 62.57 points
6 Correct 677 ms 2524 KB Output is correct (P=0.068648, F=366.2, Q=398.8) -> 66.37 points
7 Correct 868 ms 2528 KB Output is correct (P=0.104571, F=490.3, Q=523.0) -> 71.05 points
8 Correct 1090 ms 2536 KB Output is correct (P=0.158765, F=639.1, Q=664.1) -> 77.82 points
9 Correct 1238 ms 2564 KB Output is correct (P=0.2, F=731.4, Q=750.5) -> 81.49 points