Submission #1094602

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

Main

#include "bits/stdc++.h"
//#define int long long
#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> A;
vector<int> ar;

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

void update_block(int rem){
  int l=1,r=rem;
  while(l<r){
    int mid=(l+r+1)/2;
    if(fast_pow(p,mid)>=0.5) l=mid;
    else r=mid-1;
  }
  BL=l;
}

bool test_students(vector<bool> mask){
	cout << "Q ";
  for(int x:mask) cout << x;
  cout << endl << flush; 
  char answer; cin >> answer;
  return answer == 'P';
}

bool ask_range(int l,int r){
  vector<bool> cur(n,0);
  for(int i=l;i<=r;i++) cur[ar[i]]=1;
  return test_students(cur);
}

int find_first(int l,int r){
  if(l==r) return l;
  int m=(l+r)/2;
  if(ask_range(l,m)) return find_first(l,m);
  return find_first(
    m+1,r);
}

vector<bool> find_positive(){
	A.assign(n,0);
  for(int i=0;i<n;){
    update_block(n-i);
    if(!ask_range(i,i+BL-1)){
      i+=BL;
      continue;
    }
    int lmao = find_first(i,i+BL-1);
    A[ar[lmao]]=1;
    i=lmao+1;
  }
  return A;
}

void _(){
  vector<bool> GG=find_positive();
  cout << "A ";
  for(bool x:GG) cout << x;
  cout << endl << 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;
  p=1.0-p;
  update_block(n);
  ar.assign(n,0);
  iota(all(ar),0LL);
  shuffle(all(ar),rng);
  while(tc--) _();
  return 0;
}

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