oj.uz

Submission #1026416

# Submission time Handle Problem Language Result Execution time Memory
1026416 2024-07-18T05:28:20 Z 우민규(#10946) COVID tests (CEOI24_covid) C++17
45.05 / 100
 6231 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);

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() {
  if (t == 1) {
    exp_chunk[n] = 1;
  } else {
    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);
  cin >> n >> p >> t;
  for (int i = 0; i < t; ++i) {
    solve();
  }
  return 0;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
10.0 / 10.0

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

Subtask #2
35.049999996 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4782 ms 344 KB Output is correct (P=0.001, F=15.1, Q=18.1) -> 50.15 points
2 Correct 4737 ms 596 KB Output is correct (P=0.005256, F=51.1, Q=70.1) -> 36.18 points
3 Correct 4969 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=132.1) -> 35.05 points
4 Correct 5290 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=259.8) -> 37.09 points
5 Correct 5404 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=327.4) -> 38.84 points
6 Correct 5755 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=462.9) -> 43.77 points
7 Correct 5932 ms 344 KB Output is correct (P=0.104571, F=490.3, Q=607.9) -> 45.93 points
8 Correct 6231 ms 344 KB Output is correct (P=0.158765, F=639.1, Q=735.2) -> 56.20 points
9 Correct 5717 ms 344 KB Output is correct (P=0.2, F=731.4, Q=822.0) -> 60.18 points