Submission #1094642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094642		epicci23	COVID tests (CEOI24_covid)	C++17	10 / 100	7054 ms	352 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;
vector<int> sor;

bool test_students(){
  cout << "Q ";
  for(int x:cur) cout << x;
  cout << '\n' << flush; 
  char answer; cin >> answer;
  return answer == 'P';
}
 
bool Ask(){
  for(int x:sor) cur[x]=1;
  bool res = test_students();
  for(int x:sor) 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);
}
 
void 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;

     int hm = sz(g2);
     for(int j=0;j<min(hm,cur_BL);j++){
      sor.push_back(g2.back());
      g2.pop_back();
     }

     if(Ask()){
       g1.insert(end(g1),all(g2));
       g2=sor;
     }
     
     sor.clear();
    }
    else{
      int hm = sz(g1);
      for(int j=0;j<min(hm,BL);j++){
       sor.push_back(g1.back());
       g1.pop_back();
      }
      if(Ask()) g2=sor;

      sor.clear();
    }
  }
}
 
void _(){
  find_positive();
  cout << "A ";
  for(bool x:A) 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