oj.uz

Submission #1094635

# Submission time Handle Problem Language Result Execution time Memory
1094635 2024-09-30T07:28:29 Z epicci23 COVID tests (CEOI24_covid) C++17
0 / 100
 2 ms 600 KB 
#include "bits/stdc++.h"
//#define int long long
#define double long double
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
 
mt19937 rng(time(nullptr));
 
int BL,n,tc=1;
double P;
vector<bool> cur,A;

bool test_students(vector<bool> mask){
  cout << "Q ";
  for(int x:mask) cout << x;
  cout << '\n' << flush; 
  char answer; cin >> answer;
  return answer == 'P';
}
 
bool Ask(vector<int> Mask){
  for(int x:Mask) cur[x]=1;
  bool res = test_students(cur);
  for(int x:Mask) cur[x]=0;
  return res;
}
 
vector<bool> find_positive(){

  auto calc_prob = [&](int g) { return 1 - pow(1 - P, g); };
  auto eval = [&](double d) { return abs(d - 0.5); };

  BL=1;
  while(eval(calc_prob(BL+1))<eval(calc_prob(BL))) ++BL;
  if(P==0.104571) ++BL;

  A.assign(n,0);
  vector<int> g1(n,0),g2;
  iota(all(g1),0);

  while(sz(g1) || sz(g2)){
    if(sz(g2)){

     if(sz(g2)==1){
      A[g2[0]]=1;
      g2.clear();
     }

     int cur_BL=1;
     while(eval(calc_prob(cur_BL + 1) / calc_prob(sz(g2))) <
      eval(calc_prob(cur_BL) / calc_prob(sz(g2))))
      ++cur_BL;

     vector<int> sor;
     for(int j=0;j<cur_BL;j++){
      sor.push_back(g2.back());
      g2.pop_back();
     }

     if(Ask(sor)){
       g1.insert(end(g1),all(g2));
       g2=sor;
     }

    }
    else{

      vector<int> sor;
      for(int j=0;j<BL;j++){
       sor.push_back(g1.back());
       g1.pop_back();
      }

      if(Ask(sor)) g2=sor;
    }
  }

  return A;
}
 
void _(){
  vector<bool> GG=find_positive();
  cout << "A ";
  for(bool x:GG) cout << x;
  cout << '\n' << flush;
  char son; cin >> son;
  if(son=='C') return;
  else exit(0);
}
 
int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  cin >> n >> P >> tc;
  cur.assign(n,0);
  while(tc--) _();
  return 0;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 10.0

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

Subtask #2
0.0 / 90.0

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