Submission #1094640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094640		epicci23	COVID tests (CEOI24_covid)	C++17	10 / 100	7052 ms	596 KiB

Main

#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;
 
int BL,n,tc;
double P;
vector<bool> cur,A;
vector<double> Store;

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

double Fast(double x,int u){
  if(u==0) return 1.0L;
  double res=Fast(x,u/2);
  res*=res;
  if(u&1) res*=x;
  return res;
}

inline double calc_prob(int g){
  return 1.0L - Fast(1.0L - P, g);
}

inline double eval(double d){
   return abs(d - 0.5L);
}
 
vector<bool> find_positive(){
  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();
      continue;
     }

     int cur_BL = 1;
     while(eval(Store[cur_BL+1]/Store[sz(g2)]) 
      < eval(Store[cur_BL]/Store[sz(g2)]))
      ++cur_BL;

     vector<int> sor;
     int hm = sz(g2);
     for(int j=0;j<min(hm,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;
      int hm = sz(g1);
      for(int j=0;j<min(hm,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);
  Store.resize(n+5);

  for(int i=0;i<=n;i++) Store[i]=calc_prob(i);
  BL=1;
  while(eval(Store[BL+1])<eval(Store[BL])) ++BL;
  if(P==0.104571) ++BL;

  while(tc--) _();
  return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 0 / 90