oj.uz

Submission #1094618

# Submission time Handle Problem Language Result Execution time Memory
1094618 2024-09-30T07:01:10 Z epicci23 COVID tests (CEOI24_covid) C++17
0 / 100
 7000 ms 344 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;
vector<int> ar,Store;
 
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 l=1,r=n;
  while(l<r){
    int mid=(l+r+1)/2;
    if(fast_pow(p,mid)>=0.5L) l=mid;
    else r=mid-1;
  }
  Store.resize(n+5);
  l=max(150,l);
  for(int i=1;i<=n;i++) Store[i]=min(i,l);
}
 
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_range(int l,int r){
  for(int i=l;i<=r;i++) cur[ar[i]]=1;
  bool XD = test_students(cur);
  for(int i=l;i<=r;i++) cur[ar[i]]=0;
  return XD;
}
 
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;){
    BL=Store[n-i];
    if(!ask_range(i,min(n-1,i+BL-1))){
      i+=BL;
      continue;
    }
    int lmao = find_first(i,min(n-1,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 << '\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;
  p=1.0-p;
  update_block();
  ar.assign(n,0);
  cur.assign(n,0);
  iota(all(ar),0LL);
  shuffle(all(ar),rng);
  while(tc--) _();
  return 0;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 344 KB Output is correct (P=0.001, F=15.1, Q=11.0) -> 90.00 points
2 Correct 527 ms 344 KB Output is correct (P=0.005256, F=51.1, Q=46.9) -> 90.00 points
3 Correct 1044 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=97.0) -> 82.68 points
4 Correct 2520 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=235.0) -> 47.15 points
5 Correct 3512 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=330.4) -> 38.04 points
6 Correct 6080 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=569.2) -> 27.97 points
7 Execution timed out 7058 ms 344 KB Time limit exceeded
8 Halted 0 ms 0 KB -