oj.uz

Submission #1077598

# Submission time Handle Problem Language Result Execution time Memory
1077598 2024-08-27T08:14:11 Z Arturgo COVID tests (CEOI24_covid) C++14
100 / 100
 3197 ms 8524 KB 
#include <bits/stdc++.h>
using namespace std;

int N;
double P;

bool test_students(vector<bool> mask);

bool estPasse[1001][1001];
double dp[1001][1001];

double powers[1001];

double esp(int prefix, int total) {
    if(estPasse[prefix][total]) return dp[prefix][total];
    estPasse[prefix][total] = true;
    
    if(total == 0) return dp[prefix][total] = 0;

    if(prefix == 0) {
        double min_esp = INFINITY;
        for(int sz = 1;sz <= total;sz++) {
            double P_vide = powers[sz];
            min_esp = min(min_esp, 
                1 
                + esp(0, total - sz) * P_vide
                + esp(sz, total) * (1 - P_vide)
            );
        }
        return dp[prefix][total] = min_esp;
    } else if(prefix == 1) {
        return dp[prefix][total] = esp(0, total - 1);
    } else {
        double min_esp = INFINITY;
        for(int sz = 1;sz < prefix;sz++) {
            double P_vide = powers[sz] * (1 - powers[prefix - sz]) / (1 - powers[prefix]);

            min_esp = min(min_esp,
                1
                + esp(prefix - sz, total - sz) * P_vide
                + esp(sz, total) * (1 - P_vide)
            );
        }
        return dp[prefix][total] = min_esp;
    }
}

bool ask_inter(int deb, int fin) {
    vector<bool> mask(N, false);
    fill(mask.begin() + deb, mask.begin() + fin, true);
    return test_students(mask);
}

vector<bool> find_positive() {
    vector<bool> answer(N, false);
    int prefix = 0, total = N;

    while(total != 0) {
        if(prefix == 0) {
            double min_esp = INFINITY;
            int opt_sz = -1;

            for(int sz = 1;sz <= total;sz++) {
                double P_vide = powers[sz];
                double E = 
                    1 
                    + esp(0, total - sz) * P_vide
                    + esp(sz, total) * (1 - P_vide);
                
                if(E < min_esp) {
                    min_esp = E;
                    opt_sz = sz;
                }
            }

            bool ans = ask_inter(N - total, N - total + opt_sz);
            if(ans) {
                prefix = opt_sz;
            } else total -= opt_sz;
        } else if(prefix == 1) {
            answer[N - total] = true;
            prefix = 0;
            total -= 1;
        } else {
            double min_esp = INFINITY;
            int opt_sz = -1;

            for(int sz = 1;sz < prefix;sz++) {
                double P_vide = powers[sz] * (1 - powers[prefix - sz]) / (1 - powers[prefix]);
                double E = 
                    1
                    + esp(prefix - sz, total - sz) * P_vide
                    + esp(sz, total) * (1 - P_vide);
                
                if(E < min_esp) {
                    min_esp = E;
                    opt_sz = sz;
                }
            }

            bool ans = ask_inter(N - total, N - total + opt_sz);
            if(ans) {
                prefix = opt_sz;
            } else {
                prefix -= opt_sz;
                total -= opt_sz;
            }
        }
    }

    return answer;
}

void init() {
    powers[0] = 1.;
    for(int i = 1;i <= 1000;i++) {
        powers[i] = (1 - P) * powers[i - 1];
    }
}

/*
int __nbTests = 0;
vector<bool> __covid;

int main() {
    N = 1000;
    P = 0.2;
    int T = 10;

    init();
    cerr << "ESP: " << esp(0, N) << endl;

    for(int i = 0;i < T;i++) {
        __nbTests = 0;
        __covid.clear();
        for(int i = 0;i < N;i++) {
            __covid.push_back(rand() <= P * RAND_MAX);
        }

        vector<bool> answer = find_positive();
        assert(answer == __covid);

        cerr << i << ": " << __nbTests << endl;
    }
}

bool test_students(vector<bool> mask) {
    __nbTests++;
    bool ok = false;
    for(int i = 0;i < N;i++) {
        if(mask[i] && __covid[i]) ok = true;
    }
    return ok;
}

/*/

int main() {
    int T;
    scanf("%d %lf %d", &N, &P, &T);

    init();

    for (int i = 0; i < T; i++) {
        vector<bool> answer = find_positive();
        assert(answer.size() == (size_t)N);

        string answer_str(N, ' ');
        for (int j = 0; j < N; j++)
            answer_str[j] = answer[j] ? '1' : '0';

        printf("A %s\n", answer_str.c_str());
        fflush(stdout);

        char verdict;
        scanf(" %c", &verdict);
        if (verdict == 'W')
            exit(0);
    }

    return 0;
}

bool test_students(vector<bool> mask) {
    assert(mask.size() == (size_t)N);

    string mask_str(N, ' ');
    for (int i = 0; i < N; i++)
        mask_str[i] = mask[i] ? '1' : '0';

    printf("Q %s\n", mask_str.c_str());
    fflush(stdout);

    char answer;
    scanf(" %c", &answer);
    return answer == 'P';
}
//*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:160:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |     scanf("%d %lf %d", &N, &P, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:176:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         scanf(" %c", &verdict);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'bool test_students(std::vector<bool>)':
Main.cpp:195:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |     scanf(" %c", &answer);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1025 ms 8184 KB Output is correct
2 Correct 1010 ms 8272 KB Output is correct
3 Correct 989 ms 8272 KB Output is correct
4 Correct 997 ms 8316 KB Output is correct
5 Correct 1041 ms 8420 KB Output is correct
6 Correct 1004 ms 8188 KB Output is correct
7 Correct 980 ms 8272 KB Output is correct
8 Correct 977 ms 8272 KB Output is correct
9 Correct 998 ms 8244 KB Output is correct
10 Correct 958 ms 8272 KB Output is correct
11 Correct 971 ms 8272 KB Output is correct
12 Correct 967 ms 8332 KB Output is correct
13 Correct 975 ms 8284 KB Output is correct
14 Correct 1004 ms 8524 KB Output is correct
15 Correct 950 ms 8272 KB Output is correct
16 Correct 998 ms 8476 KB Output is correct
17 Correct 964 ms 8384 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 8360 KB Output is correct (P=0.001, F=15.1, Q=10.8) -> 90.00 points
2 Correct 1084 ms 8288 KB Output is correct (P=0.005256, F=51.1, Q=46.3) -> 90.00 points
3 Correct 1220 ms 8272 KB Output is correct (P=0.011546, F=94.9, Q=90.5) -> 90.00 points
4 Correct 1491 ms 8224 KB Output is correct (P=0.028545, F=191.5, Q=187.7) -> 90.00 points
5 Correct 1676 ms 8276 KB Output is correct (P=0.039856, F=246.3, Q=243.7) -> 90.00 points
6 Correct 1965 ms 8280 KB Output is correct (P=0.068648, F=366.2, Q=364.2) -> 90.00 points
7 Correct 2402 ms 8312 KB Output is correct (P=0.104571, F=490.3, Q=488.2) -> 90.00 points
8 Correct 2860 ms 8272 KB Output is correct (P=0.158765, F=639.1, Q=633.1) -> 90.00 points
9 Correct 3197 ms 8312 KB Output is correct (P=0.2, F=731.4, Q=729.3) -> 90.00 points