Submission #1256419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256419		bynix	COVID tests (CEOI24_covid)	C++20	73.95 / 100	518 ms	440 KiB

Main

#include "bits/stdc++.h"
using namespace std;

string allzero(1000, '0');
vector<int> res;
int ct;

void upd(int l, int r, int v){
  for (int i = l; i <= r; i++) res[i] = v;
  ct += r - l + 1;
}

int query(int l, int r){
  string q = allzero;
  for (int i = l; i <= r; i++) q[i] = '1';
  cout << "Q " << q << endl;
  char v; cin >> v;
  return (v == 'P');
}

void done(){
  cout << "A ";
  for (int i = 0; i < 1000; i++) cout << res[i]; 
  cout << endl;
  char t; cin >> t;
}

int main(){
  int N, T; double P;
  cin >> N >> P >> T;
  cin.tie(0)->sync_with_stdio(0);

  int S = 1000; 
  for (int i = 1000; i >= 1; i--)
    if (1000%i == 0){
      if (P*(i) < 0.5){
        S = i; break;
      }
    }

  if (T == 1){
    res.clear(); res.resize(N, 0);
    ct = 0;
    for (int i = 0; i < N; i++) res[i] = query(i, i);
    done();
  } else {
    while (T--){
      res.clear(); res.resize(N, 0); ct = 0;
      int l = 0, r = min(N, l + S - 1);
      while (ct < N){
        if (query(l, r)){
          int L = l, R = r;
          while (L < R){
            int mid = (L+R)/2;
            if (query(L, mid)) R = mid;
            else upd(L, mid, 0), L = mid + 1;
          }
          upd(L, R, 1);
          l = L+1, r = min(N-1,L+S);
        } else {
          upd(l, r, 0);
          l += S, r += S, l = min(l, N-1), r = min(r, N-1);
        }
      }
      done();
    }
  }

}

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