oj.uz

Submission #1078238

# Submission time Handle Problem Language Result Execution time Memory
1078238 2024-08-27T14:24:52 Z anton COVID tests (CEOI24_covid) C++17
80.08 / 100
 2195 ms 11248 KB 
#include<bits/stdc++.h>
using namespace std;

/// You may use:

// The number of students
int N;

// The probability any given student is positive
double P;

int group_sz =1;
// This function performs a test on a subset of samples.
// Its argument is a vector of Booleans of length N,
// where the i-th element is true if the i-th sample should be added to the mix.
// It returns true if (and only if) at least one of the samples in the mix is positive.
bool test_students(std::vector<bool> mask) {
    assert(mask.size() == (size_t)N);

    std::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';
}

/// You should implement:

// This function will be called once for each test instance.
// It should use test_students to determine which samples are positive.
// It must return a vector of Booleans of length N,
// where the i-th element is true if and only if the i-th sample is positive.
bool test_single(int u){
    vector<bool> mask(N, false);
    mask[u] = true;
    return test_students(mask);
}

bool test_inter(int l, int r){
    vector<bool> mask(N, false);
    for(int i = l; i<=r; i++){
        mask[i] = true;
    }
    return test_students(mask);
}

int split_len[1001][1001];
double expected_turns[1001][1001];
std::vector<bool> find_positive() {
    std::vector<bool> answer(N);

    int total = N;
    int pref = 0;
    while(total>0){
        //cout<<total<<" "<<pref<<" "<<expected_turns[total][pref]<<endl;
        if(split_len[total][pref] == 0){
            answer[N-total] = true;
            total --;
            pref = 0;
        }
        else{
            int len = split_len[total][pref];
            bool is_one = test_inter(N-total, N-total+len-1);
            if(is_one){
                pref = len;
            }
            else{
                total-=len;

                if(len<pref){
                    pref-=len;
                }
            }
        }
    }
    
    return answer;
}
double memo[1001];

double mpow(int deg){
    return memo[deg];
}
double P_1(int len){
    return 1.-mpow(len);
}
double P_none(int len){
    return mpow(len);
}

void chmax(int total, int pref, int test_len, double expected){
    if(expected_turns[total][pref]>expected){
        split_len[total][pref] = test_len;
        expected_turns[total][pref] = expected;
    }
}
int main() {
    int T;
    scanf("%d %lf %d", &N, &P, &T);

    memo[0] =1.;
    for(int i =1; i<1001; i++){
        memo[i] = memo[i-1] * 1.-P;
    }
    // You may perform any extra initialization here.
    
    for(int total = 0; total<=N; total++){
        for(int pref=  0; pref<=total; pref++){
            expected_turns[total][pref] = 1e18;
        }
    }

    expected_turns[0][0] = 0.;
    for(int total = 1; total<=N; total++){
        bool zero = false;
        for(int pref=  1; !zero; pref= (pref+1)%(total+1)){
            if(pref==0){
                for(int test_len = 1; test_len<=total; test_len++){
                    double expected=  P_1(test_len) * expected_turns[total][test_len] + P_none(test_len) * expected_turns[total-test_len][0] + 1.;
                    chmax(total, pref, test_len, expected);
                }
            }
            else{
                if(pref==1){
                    chmax(total, pref, 0, expected_turns[total-1][0]);
                }
                else{
                    for(int test_len = 1; test_len<pref; test_len++){
                        double p_cur = P_1(pref);
                        double P_left = P_1(test_len)/p_cur;
                        double expected = P_left * expected_turns[total][test_len] +(1-P_left) * expected_turns[total-test_len][pref-test_len] + 1.;
                        chmax(total, pref, test_len, expected);
                    }
                }
            }
            if(pref == 0){
                zero = true;
            }
        }
    }
    for (int i = 0; i < T; i++) {
        std::vector<bool> answer = find_positive();
        assert(answer.size() == (size_t)N);

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

Compilation message

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

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 343 ms 11236 KB Output is correct
2 Correct 323 ms 11084 KB Output is correct
3 Correct 355 ms 11236 KB Output is correct
4 Correct 337 ms 11248 KB Output is correct
5 Correct 345 ms 11144 KB Output is correct
6 Correct 334 ms 11088 KB Output is correct
7 Correct 340 ms 11088 KB Output is correct
8 Correct 339 ms 11228 KB Output is correct
9 Correct 360 ms 11088 KB Output is correct
10 Correct 316 ms 11216 KB Output is correct
11 Correct 361 ms 11088 KB Output is correct
12 Correct 337 ms 11088 KB Output is correct
13 Correct 378 ms 11084 KB Output is correct
14 Correct 334 ms 11244 KB Output is correct
15 Correct 347 ms 11088 KB Output is correct
16 Correct 335 ms 11088 KB Output is correct
17 Correct 277 ms 11004 KB Output is correct

Subtask #2
70.080000003 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 11108 KB Output is correct (P=0.001, F=15.1, Q=11.7) -> 90.00 points
2 Correct 459 ms 11092 KB Output is correct (P=0.005256, F=51.1, Q=48.9) -> 90.00 points
3 Correct 582 ms 11088 KB Output is correct (P=0.011546, F=94.9, Q=94.6) -> 90.00 points
4 Correct 821 ms 11084 KB Output is correct (P=0.028545, F=191.5, Q=198.0) -> 79.24 points
5 Correct 1016 ms 11164 KB Output is correct (P=0.039856, F=246.3, Q=263.8) -> 70.08 points
6 Correct 1288 ms 11184 KB Output is correct (P=0.068648, F=366.2, Q=381.7) -> 76.97 points
7 Correct 1553 ms 11132 KB Output is correct (P=0.104571, F=490.3, Q=502.9) -> 81.61 points
8 Correct 1890 ms 11024 KB Output is correct (P=0.158765, F=639.1, Q=654.2) -> 82.23 points
9 Correct 2195 ms 11092 KB Output is correct (P=0.2, F=731.4, Q=756.3) -> 79.21 points