Submission #1060774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060774		Alid	COVID tests (CEOI24_covid)	C++17	70.28 / 100	1474 ms	756 KiB

Main

#include <vector>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string>
using namespace std;

bool test_pupils(vector<int>);

const int NMAX = 112345;

int opt_ask[NMAX][2];
double opt_val[NMAX][2];

void f(vector<int> &out, int start, int len, bool 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);

    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)
{

    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;
                }
            }
        }

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

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