oj.uz

Submission #1077615

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

bool test_students(vector<bool> mask);
double esp(int prefix, int total);

int N;
double P;
bool estPasse[1001][1001];
double dp[1001][1001];
double powers[1001];

pair<double, int> opt_no_prefix(int total) {
    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;
        }
    }

    return {min_esp, opt_sz};
}

pair<double, int> opt_prefix(int prefix, int total) {
    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;
        }
    }

    return {min_esp, opt_sz};
}

double esp(int prefix, int total) {
    if(estPasse[prefix][total]) return dp[prefix][total];
    estPasse[prefix][total] = true;
    
    double& answer = dp[prefix][total];
    if(total == 0) return answer = 0;
    if(prefix == 0) return answer = opt_no_prefix(total).first;
    if(prefix == 1) return answer = esp(0, total - 1);
    return answer = opt_prefix(prefix, total).first;
}

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) {
            int opt_sz = opt_no_prefix(total).second;

            if(ask_inter(N - total, N - total + opt_sz)) {
                prefix = opt_sz;
            } else total -= opt_sz;
        } else if(prefix == 1) {
            answer[N - total] = true;
            prefix = 0;
            total -= 1;
        } else {
            int opt_sz = opt_prefix(prefix, total).second;
            
            if(ask_inter(N - total, N - total + opt_sz)) 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 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:102:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     scanf("%d %lf %d", &N, &P, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         scanf(" %c", &verdict);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'bool test_students(std::vector<bool>)':
Main.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |     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 1276 ms 8344 KB Output is correct
2 Correct 1357 ms 8272 KB Output is correct
3 Correct 1401 ms 8272 KB Output is correct
4 Correct 1449 ms 8288 KB Output is correct
5 Correct 1407 ms 8228 KB Output is correct
6 Correct 1435 ms 8180 KB Output is correct
7 Correct 1372 ms 8176 KB Output is correct
8 Correct 1356 ms 8328 KB Output is correct
9 Correct 1332 ms 8272 KB Output is correct
10 Correct 1269 ms 8500 KB Output is correct
11 Correct 1317 ms 8364 KB Output is correct
12 Correct 1309 ms 8268 KB Output is correct
13 Correct 1298 ms 8360 KB Output is correct
14 Correct 1292 ms 8220 KB Output is correct
15 Correct 1263 ms 8304 KB Output is correct
16 Correct 1312 ms 8364 KB Output is correct
17 Correct 1277 ms 8316 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1296 ms 8272 KB Output is correct (P=0.001, F=15.1, Q=10.8) -> 90.00 points
2 Correct 1400 ms 8152 KB Output is correct (P=0.005256, F=51.1, Q=46.3) -> 90.00 points
3 Correct 1560 ms 8208 KB Output is correct (P=0.011546, F=94.9, Q=90.5) -> 90.00 points
4 Correct 1838 ms 8268 KB Output is correct (P=0.028545, F=191.5, Q=187.7) -> 90.00 points
5 Correct 2021 ms 8180 KB Output is correct (P=0.039856, F=246.3, Q=243.7) -> 90.00 points
6 Correct 2475 ms 8272 KB Output is correct (P=0.068648, F=366.2, Q=364.2) -> 90.00 points
7 Correct 3053 ms 8324 KB Output is correct (P=0.104571, F=490.3, Q=488.2) -> 90.00 points
8 Correct 3313 ms 8220 KB Output is correct (P=0.158765, F=639.1, Q=633.1) -> 90.00 points
9 Correct 3409 ms 8272 KB Output is correct (P=0.2, F=731.4, Q=729.3) -> 90.00 points