oj.uz

Submission #1060774

# Submission time Handle Problem Language Result Execution time Memory
1060774 2024-08-15T22:31:26 Z Alid COVID tests (CEOI24_covid) C++17
70.28 / 100
 1474 ms 756 KB 
#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

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 / 0.0

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 592 KB Output is correct
2 Correct 45 ms 592 KB Output is correct
3 Correct 54 ms 432 KB Output is correct
4 Correct 42 ms 432 KB Output is correct
5 Correct 49 ms 596 KB Output is correct
6 Correct 46 ms 436 KB Output is correct
7 Correct 32 ms 592 KB Output is correct
8 Correct 28 ms 592 KB Output is correct
9 Correct 38 ms 592 KB Output is correct
10 Correct 28 ms 600 KB Output is correct
11 Correct 29 ms 756 KB Output is correct
12 Correct 29 ms 592 KB Output is correct
13 Correct 30 ms 444 KB Output is correct
14 Correct 29 ms 344 KB Output is correct
15 Correct 29 ms 756 KB Output is correct
16 Correct 17 ms 488 KB Output is correct
17 Correct 18 ms 344 KB Output is correct

Subtask #2
60.280000002 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 600 KB Output is correct (P=0.001, F=15.1, Q=13.2) -> 90.00 points
2 Correct 131 ms 716 KB Output is correct (P=0.005256, F=51.1, Q=55.9) -> 65.42 points
3 Correct 234 ms 464 KB Output is correct (P=0.011546, F=94.9, Q=106.6) -> 60.28 points
4 Correct 458 ms 712 KB Output is correct (P=0.028545, F=191.5, Q=214.2) -> 61.05 points
5 Correct 575 ms 464 KB Output is correct (P=0.039856, F=246.3, Q=273.3) -> 62.57 points
6 Correct 835 ms 476 KB Output is correct (P=0.068648, F=366.2, Q=398.8) -> 66.37 points
7 Correct 1008 ms 692 KB Output is correct (P=0.104571, F=490.3, Q=523.0) -> 71.05 points
8 Correct 1315 ms 488 KB Output is correct (P=0.158765, F=639.1, Q=664.1) -> 77.82 points
9 Correct 1474 ms 596 KB Output is correct (P=0.2, F=731.4, Q=750.5) -> 81.49 points