oj.uz

답안 #1094626

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094626 2024-09-30T07:07:48 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*=5;
  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,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 << '\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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 98 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 344 KB Output is correct (P=0.001, F=15.1, Q=10.8) -> 90.00 points
2 Correct 553 ms 344 KB Output is correct (P=0.005256, F=51.1, Q=51.8) -> 85.32 points
3 Correct 1139 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=104.9) -> 63.31 points
4 Correct 2359 ms 340 KB Output is correct (P=0.028545, F=191.5, Q=225.1) -> 52.88 points
5 Correct 3134 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=302.1) -> 47.21 points
6 Correct 4801 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=461.2) -> 44.17 points
7 Correct 6493 ms 344 KB Output is correct (P=0.104571, F=490.3, Q=629.4) -> 42.16 points
8 Execution timed out 7052 ms 344 KB Time limit exceeded
9 Halted 0 ms 0 KB -