oj.uz

Submission #1077594

# Submission time Handle Problem Language Result Execution time Memory
1077594 2024-08-27T08:11:14 Z Arturgo COVID tests (CEOI24_covid) C++14
10 / 100
 4295 ms 8364 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;
}

/*

int __nbTests = 0;
vector<bool> __covid;

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

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

    cerr << "ESP: " << esp(0, 1000) << 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);

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

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 1008 ms 8320 KB Output is correct
2 Correct 957 ms 8356 KB Output is correct
3 Correct 930 ms 8272 KB Output is correct
4 Correct 926 ms 8228 KB Output is correct
5 Correct 937 ms 8272 KB Output is correct
6 Correct 945 ms 8364 KB Output is correct
7 Correct 949 ms 8340 KB Output is correct
8 Correct 941 ms 8272 KB Output is correct
9 Correct 938 ms 8316 KB Output is correct
10 Correct 965 ms 8348 KB Output is correct
11 Correct 972 ms 8272 KB Output is correct
12 Correct 957 ms 8352 KB Output is correct
13 Correct 962 ms 8204 KB Output is correct
14 Correct 961 ms 8188 KB Output is correct
15 Correct 933 ms 8240 KB Output is correct
16 Correct 932 ms 8284 KB Output is correct
17 Correct 943 ms 8272 KB Output is correct

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Incorrect 4295 ms 8272 KB Incorrect
2 Halted 0 ms 0 KB -