oj.uz

Submission #1040481

# Submission time Handle Problem Language Result Execution time Memory
1040481 2024-08-01T05:53:58 Z isaachew COVID tests (CEOI24_covid) C++17
94.08 / 100
 1241 ms 600 KB 
#include <bits/stdc++.h>
/*
 Bernoulli process; attempt to split set into half every query
 */
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,t;
    double p;
    std::cin>>n>>p>>t;
    std::vector<double> bsvals;
    for(int i=0;i<=n;i++){
        bsvals.push_back(pow(1-p,i));
    }
    while(t--){
        int ind=0;
        std::vector<int> sol(n);
        while(ind<n){
            int lnum=0,unum=n-ind+1;//number of 0s before 1 or end
            
            while(lnum+1<unum){
                double midprob=-(bsvals[unum]+bsvals[lnum])/2;//prob there are no more cases
                int lhnum=lnum+1,uhnum=unum;
                while(lhnum+1<uhnum){
                    int mnum=(lhnum+uhnum)/2;
                    double mprob=-bsvals[mnum];
                    if(mprob<midprob){
                        lhnum=mnum;
                    }else{
                        uhnum=mnum;
                    }
                }
                int qnum;
                if(std::abs(-bsvals[uhnum]-midprob)<std::abs(-bsvals[lhnum]-midprob)){
                    qnum=uhnum;
                }else{
                    qnum=lhnum;
                }
                std::string mstr(n,'0');
                std::cout<<"Q ";
                for(int i=ind;i<ind+qnum;i++){
                    mstr[i]='1';
                }
                std::cout<<mstr;
                std::cout<<'\n';
                std::cout.flush();
                char c;
                std::cin>>c;
                if(c=='N'){
                    lnum=qnum;
                }else{
                    unum=qnum;
                }
            }
            ind+=lnum;
            sol[ind]=1;
            ind++;
        }
        std::cout<<"A ";
        std::string mstr(n,'0');
        for(int i=0;i<n;i++){
            mstr[i]='0'+sol[i];
        }
        std::cout<<mstr<<'\n';
        std::cout.flush();
        char c;
        std::cin>>c;
        if(c=='W')return 0;
    }
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 4 ms 344 KB Output is correct
15 Correct 4 ms 344 KB Output is correct
16 Correct 4 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct

Subtask #2
84.079999998 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 344 KB Output is correct (P=0.001, F=15.1, Q=15.1) -> 90.00 points
2 Correct 88 ms 344 KB Output is correct (P=0.005256, F=51.1, Q=52.0) -> 84.08 points
3 Correct 169 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=95.2) -> 88.88 points
4 Correct 341 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=190.9) -> 90.00 points
5 Correct 452 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=247.5) -> 88.28 points
6 Correct 646 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=366.8) -> 89.41 points
7 Correct 879 ms 344 KB Output is correct (P=0.104571, F=490.3, Q=492.9) -> 88.13 points
8 Correct 1135 ms 344 KB Output is correct (P=0.158765, F=639.1, Q=633.7) -> 90.00 points
9 Correct 1241 ms 344 KB Output is correct (P=0.2, F=731.4, Q=729.7) -> 90.00 points