oj.uz

답안 #1078223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078223 2024-08-27T14:14:31 Z oscar1f COVID tests (CEOI24_covid) C++17
100 / 100
 2079 ms 11344 KB 
#include<bits/stdc++.h>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;

/// You may use:

// The number of students
const int TAILLE_MAX=1000+5;
const double INFINI=1e9;
int N,nbTest;
vector<bool> rep;
vector<bool> attendu;
double puisP[TAILLE_MAX],puis1P[TAILLE_MAX];
double memo[TAILLE_MAX][TAILLE_MAX];
int suiv[TAILLE_MAX][TAILLE_MAX];

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

// 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(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';
}

/*bool test_students(vector<bool> mask) {
    nbTest++;
    bool ans=false;
    for (int i=0;i<N;i++) {
        if (mask[i] and attendu[i]) {
            ans=true;
        }
    }
    return ans;
}*/

bool askQuest(int deb,int fin) {
    vector<bool> quest(N);
    for (int i=deb;i<=fin;i++) {
        quest[i]=true;
    }
    return test_students(quest);
}

void dyna(int deb,int fin,int assure) {
    if (deb>fin) {
        return;
    }
    if (assure==1) {
        rep[deb]=true;
        dyna(deb+1,fin,0);
    }
    else {
        int taille=fin-deb+1;
        if (askQuest(deb,deb+suiv[assure][taille]-1)) {
            dyna(deb,fin,suiv[assure][taille]);
        }
        else if (assure==0) {
            dyna(deb+suiv[assure][taille],fin,0);
        }
        else {
            dyna(deb+suiv[assure][taille],fin,assure-suiv[assure][taille]);
        }
    }
}


/*void S9() {
    taille=8;
    for (int i=0;i<N;i+=taille) {
        bool trouve;
        vector<bool> quest(N);
        for (int j=i;j<i+taille;j++) {
            if (!rep[j]) {
                quest[j]=true;
            }
        }
        if (test_students(quest)) {
            trouve=
        }
        while (trouve) {
            trouve=dicho(i,min(i+taille-1,N-1),false);
        }
    }
}*/

/// 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.
vector<bool> find_positive() {
    rep.clear();
    rep.resize(N,false);
    dyna(0,N-1,0);
    return rep;
}

void init() {
    puisP[0]=1;
    puis1P[0]=1;
    for (int i=1;i<TAILLE_MAX;i++) {
        puisP[i]=puisP[i-1]*P;
        puis1P[i]=puis1P[i-1]*(1.0-P);
    }
    double esper,probGau;
    for (int taille=1;taille<TAILLE_MAX;taille++) {
        memo[1][taille]=memo[0][taille-1];
        for (int assure=2;assure<=taille;assure++) {
            memo[assure][taille]=INFINI;
            for (int i=1;i<assure;i++) {
                probGau=(1-puis1P[i])/(1-puis1P[assure]);
                esper=1.0+probGau*memo[i][taille]+(1-probGau)*memo[assure-i][taille-i];
                //cout<<esper<<endl;
                if (esper<memo[assure][taille]) {
                    memo[assure][taille]=esper;
                    suiv[assure][taille]=i;
                }
            }
        }
        memo[0][taille]=INFINI;
        for (int i=1;i<=taille;i++) {
            esper=1.0+(1.0-puis1P[i])*memo[i][taille]+puis1P[i]*memo[0][taille-i];
            //cout<<esper<<endl;
            if (esper<memo[0][taille]) {
                memo[0][taille]=esper;
                suiv[0][taille]=i;
            }
        }
    }
    /*for (int i=0;i<TAILLE_MAX;i++) {
        for (int j=0;j<TAILLE_MAX;j++) {
            cout<<memo[i][j]<<"  ";
        }
        cout<<endl;
    }
    for (int i=0;i<TAILLE_MAX;i++) {
        cout<<memo[0][i]<<" ";
    }*/
    //cout<<memo[0][1000]<<endl;
}

int main() {
    int T;
    scanf("%d %lf %d", &N, &P, &T);
    init();
    // You may perform any extra initialization here.

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

/*int main() {
    int T;
    cin>>N>>P>>T;
    // You may perform any extra initialization here.
    init();
    char val;
    for (int i = 0; i < T; i++) {
        attendu.clear();
        for (int j=0;j<N;j++) {
            cin>>val;
            //cout<<val;
            attendu.push_back(val=='1');
        }
        std::vector<bool> answer = find_positive();
        for (int j=0;j<N;j++) {
            if (attendu[j]!=answer[j]) {
                cout<<"PROBLEME"<<" "<<i<<" "<<j<<endl;
                return 0;
            }
        }
    }
    cout<<nbTest/T<<endl;
    cout<<"OK"<<endl;
    return 0;
}*/

Compilation message

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

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 327 ms 11316 KB Output is correct

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 339 ms 11088 KB Output is correct
2 Correct 334 ms 11120 KB Output is correct
3 Correct 331 ms 11272 KB Output is correct
4 Correct 335 ms 11088 KB Output is correct
5 Correct 346 ms 11268 KB Output is correct
6 Correct 343 ms 11188 KB Output is correct
7 Correct 349 ms 11088 KB Output is correct
8 Correct 335 ms 11092 KB Output is correct
9 Correct 342 ms 11084 KB Output is correct
10 Correct 355 ms 11088 KB Output is correct
11 Correct 345 ms 11272 KB Output is correct
12 Correct 337 ms 11088 KB Output is correct
13 Correct 347 ms 11088 KB Output is correct
14 Correct 334 ms 11252 KB Output is correct
15 Correct 346 ms 11168 KB Output is correct
16 Correct 373 ms 11208 KB Output is correct
17 Correct 330 ms 7212 KB Output is correct

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 370 ms 11088 KB Output is correct (P=0.001, F=15.1, Q=10.8) -> 90.00 points
2 Correct 462 ms 11088 KB Output is correct (P=0.005256, F=51.1, Q=46.3) -> 90.00 points
3 Correct 586 ms 11232 KB Output is correct (P=0.011546, F=94.9, Q=90.5) -> 90.00 points
4 Correct 809 ms 11288 KB Output is correct (P=0.028545, F=191.5, Q=187.7) -> 90.00 points
5 Correct 919 ms 11316 KB Output is correct (P=0.039856, F=246.3, Q=243.7) -> 90.00 points
6 Correct 1256 ms 11344 KB Output is correct (P=0.068648, F=366.2, Q=364.2) -> 90.00 points
7 Correct 1500 ms 11088 KB Output is correct (P=0.104571, F=490.3, Q=488.2) -> 90.00 points
8 Correct 1892 ms 11120 KB Output is correct (P=0.158765, F=639.1, Q=633.1) -> 90.00 points
9 Correct 2079 ms 11088 KB Output is correct (P=0.2, F=731.4, Q=729.3) -> 90.00 points