Submission #1040481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040481		isaachew	COVID tests (CEOI24_covid)	C++17	94.08 / 100	1241 ms	600 KiB

Main

#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
• Subtask 1: 10 / 10
• Subtask 2: 84.07999999799999 / 90