oj.uz

Submission #1026413

# Submission time Handle Problem Language Result Execution time Memory
1026413 2024-07-18T05:23:56 Z 우민규(#10946) COVID tests (CEOI24_covid) C++17
35.05 / 100
 6278 ms 460 KB 
#include <bits/stdc++.h>
using namespace std;

int n, t;
double p;
vector<double> exp_query(1001);
vector<int> exp_chunk(1001);

string ans;
int qcnt = 0;

bool ask(string& s) {
  //   qcnt += 1;
  //   for (int i = 0; i < ans.size(); ++i)
  //     if (s[i] == '1' && ans[i] == '1') return true;
  //   return false;
  cout << "Q " << s << endl;
  char c;
  cin >> c;
  return c == 'P';
}

string ill;

void solve(int l, int r) {
  if (r - l == 1) {
    // if n > 1, this must be from a recursive solve call
    // thus, there must be a patient in [l, r), which means that l is ill
    ill[l] = '1';
    return;
  }
  int chunks = exp_chunk[r - l];
  for (int i = l; i < r; i += chunks) {
    string cur(n, '0');
    for (int j = i; j < i + chunks && j < r; ++j) {
      cur[j] = '1';
    }
    if (ask(cur)) {
      solve(i, min(r, i + chunks));
    }
  }
}

void solve() {
  exp_query[1] = 1, exp_chunk[1] = 1;
  for (int i = 2; i <= n; ++i) {
    double expected = 999999;
    int expected_chunk = -1;
    for (int k = 1; k < i; ++k) {
      int chunks = (i + (k - 1)) / k;
      double prob = 1 - pow(1 - p, k);
      double cur_exp =
          (chunks * prob / (1 - pow(1 - p, i))) * exp_query[k] + chunks;
      if (cur_exp < expected) {
        expected_chunk = k;
        expected = cur_exp;
      }
    }
    exp_query[i] = expected;
    exp_chunk[i] = expected_chunk;
  }
  ill = string(n, '0');
  solve(0, n);
  cout << "A " << ill << endl;
  char c;
  cin >> c;
  if (c == 'C') return;
  // WA
  exit(EXIT_SUCCESS);
  //   mt19937_64 gen(6974);
  //   for (auto p : {0.001, 0.005256, 0.011546, 0.028545, 0.039856, 0.068648,
  //                  0.104571, 0.158765, 0.2}) {
  //     exp_query[1] = 0, exp_chunk[1] = 1;
  //     for (int i = 2; i < 1001; ++i) {
  //       double expected = 999999;
  //       int expected_chunk = -1;
  //       for (int k = 1; k < i; ++k) {
  //         int chunks = (i + (k - 1)) / k;
  //         double prob = 1 - pow(1 - p, k);
  //         double cur_exp =
  //             (chunks * prob / (1 - pow(1 - p, i))) * exp_query[k] + chunks;
  //         if (cur_exp < expected) {
  //           expected_chunk = k;
  //           expected = cur_exp;
  //         }
  //       }
  //       exp_query[i] = expected;
  //       exp_chunk[i] = expected_chunk;
  //     }
  //     cout << fixed << setprecision(3) << p << ":\t" << exp_chunk[n] << "\t"
  //          << exp_query[n] << "\n";
  //     uniform_real_distribution<double> distrib(0, 1);
  //     int tot_q = 0;
  //     for (int t = 0; t < 1000; ++t) {
  //       ans = string(n, '0');
  //       qcnt = 0;
  //       for (int i = 0; i < ans.size(); ++i)
  //         if (distrib(gen) < p) ans[i] = '1';
  //       if (ans == string(n, '0')) {
  //         t--;
  //         continue;
  //       }
  //       solve(0, n);
  //       tot_q += qcnt;
  //     }
  //     cout << "res:\t" << tot_q << "\t" << (double)tot_q / 1000 << "\n";
  //   }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;
  cin >> n >> p >> t;
  while (t--) {
    solve();
  }
  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 Correct 32 ms 344 KB Output is correct
2 Correct 32 ms 344 KB Output is correct
3 Correct 32 ms 344 KB Output is correct
4 Correct 31 ms 344 KB Output is correct
5 Correct 33 ms 344 KB Output is correct
6 Correct 31 ms 344 KB Output is correct
7 Correct 26 ms 456 KB Output is correct
8 Correct 21 ms 460 KB Output is correct
9 Correct 26 ms 344 KB Output is correct
10 Correct 20 ms 344 KB Output is correct
11 Correct 19 ms 456 KB Output is correct
12 Correct 26 ms 460 KB Output is correct
13 Correct 23 ms 344 KB Output is correct
14 Correct 19 ms 344 KB Output is correct
15 Correct 21 ms 460 KB Output is correct
16 Correct 10 ms 344 KB Output is correct
17 Execution timed out 3583 ms 344 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -

Subtask #2
35.049999996 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4449 ms 344 KB Output is correct (P=0.001, F=15.1, Q=18.1) -> 50.15 points
2 Correct 4612 ms 344 KB Output is correct (P=0.005256, F=51.1, Q=70.1) -> 36.18 points
3 Correct 4714 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=132.1) -> 35.05 points
4 Correct 5082 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=259.8) -> 37.09 points
5 Correct 4980 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=327.4) -> 38.84 points
6 Correct 5522 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=462.9) -> 43.77 points
7 Correct 5901 ms 456 KB Output is correct (P=0.104571, F=490.3, Q=607.9) -> 45.93 points
8 Correct 6050 ms 344 KB Output is correct (P=0.158765, F=639.1, Q=735.2) -> 56.20 points
9 Correct 6278 ms 448 KB Output is correct (P=0.2, F=731.4, Q=822.0) -> 60.18 points