oj.uz

Submission #1026402

# Submission time Handle Problem Language Result Execution time Memory
1026402 2024-07-18T05:04:29 Z 우민규(#10946) COVID tests (CEOI24_covid) C++17
39.65 / 100
 3881 ms 596 KB 
#include <bits/stdc++.h>
using namespace std;

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

bool ask(string& s) {
  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 * exp_query[k] + 1);
      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);
  //   for (auto p : {0.001, 0.005256, 0.011546, 0.028545, 0.039856, 0.068648,
  //                  0.104571, 0.158765, 0.2}) {
  //     vector<double> exp(1001);
  //     vector<int> exp_chunk(1001);
  //     exp[1] = 1, 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 * exp[k] + 1);
  //         if (cur_exp < expected) {
  //           expected_chunk = k;
  //           expected = cur_exp;
  //         }
  //       }
  //       exp[i] = expected;
  //       exp_chunk[i] = expected_chunk;
  //     }
  //     cout << p << ": " << exp[1000] << " " << exp_chunk[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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 344 KB Output is correct
2 Correct 17 ms 344 KB Output is correct
3 Correct 18 ms 460 KB Output is correct
4 Correct 15 ms 344 KB Output is correct
5 Correct 18 ms 344 KB Output is correct
6 Correct 17 ms 344 KB Output is correct
7 Correct 12 ms 344 KB Output is correct
8 Correct 13 ms 596 KB Output is correct
9 Correct 17 ms 344 KB Output is correct
10 Correct 11 ms 344 KB Output is correct
11 Correct 17 ms 344 KB Output is correct
12 Correct 14 ms 344 KB Output is correct
13 Correct 14 ms 344 KB Output is correct
14 Correct 15 ms 344 KB Output is correct
15 Correct 13 ms 344 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct

Subtask #2
29.649999996 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2419 ms 460 KB Output is correct (P=0.001, F=15.1, Q=17.7) -> 53.29 points
2 Correct 2664 ms 344 KB Output is correct (P=0.005256, F=51.1, Q=75.3) -> 31.10 points
3 Correct 2961 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=143.0) -> 29.73 points
4 Correct 3431 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=286.3) -> 30.20 points
5 Correct 2879 ms 464 KB Output is correct (P=0.039856, F=246.3, Q=371.6) -> 29.65 points
6 Correct 3130 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=513.8) -> 34.45 points
7 Correct 3370 ms 344 KB Output is correct (P=0.104571, F=490.3, Q=689.8) -> 34.25 points
8 Correct 3619 ms 456 KB Output is correct (P=0.158765, F=639.1, Q=851.1) -> 38.68 points
9 Correct 3881 ms 344 KB Output is correct (P=0.2, F=731.4, Q=990.9) -> 37.20 points