| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1026706 |
2024-07-18T09:26:38 Z |
우민규(#10946) |
COVID tests (CEOI24_covid) |
C++17 |
|
1992 ms |
3928 KB |
#include <bits/stdc++.h>
using namespace std;
int n, t;
double p;
vector<double> exp_query(1001);
vector<int> exp_chunk(1001);
vector<double> exp_exist_query(1001), exp_idk_query(1001);
vector<int> exp_exist_chunk(1001), exp_idk_chunk(1001);
vector<bool> did_check_all(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;
mt19937_64 gen(6974);
vector<int> to_ask_next;
bool is_tc1 = false;
void solve(vector<int> candidate, bool certain_exists = false) {
if (candidate.size() == 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
string cur(n, '0');
cur[candidate[0]] = '1';
if (certain_exists || ask(cur)) ill[candidate[0]] = '1';
return;
}
if (did_check_all[candidate.size()] && !certain_exists) {
string cur(n, '0');
for (auto e : candidate) cur[e] = '1';
if (ask(cur)) solve(candidate, true);
return;
}
int chunk = certain_exists ? exp_exist_chunk[candidate.size()]
: exp_idk_chunk[candidate.size()];
string cur(n, '0');
vector<int> next_candidate;
for (int j = 0; j < chunk; ++j) {
cur[candidate.back()] = '1';
next_candidate.push_back(candidate.back());
candidate.pop_back();
}
if (!is_tc1 && !certain_exists)
to_ask_next.insert(to_ask_next.end(), candidate.begin(), candidate.end());
if (ask(cur)) {
solve(next_candidate, true);
if (is_tc1 || certain_exists) solve(candidate, false);
} else {
if (is_tc1 || certain_exists) solve(candidate, certain_exists);
}
}
void upd(double& a, int& b, double c, int d) {
if (a > c) {
a = c;
b = d;
}
}
void solve() {
ill = string(n, '0');
vector<int> candidates(n);
iota(candidates.begin(), candidates.end(), 0);
while (!candidates.empty()) {
// shuffle arr
for (int i = candidates.size() - 1; i > 0; --i)
swap(candidates[i], candidates[gen() % (i + 1)]);
solve(candidates);
candidates.clear();
candidates.swap(to_ask_next);
}
cout << "A " << ill << endl;
char c;
cin >> c;
if (c == 'C') return;
// WA
exit(EXIT_SUCCESS);
// mt19937_64 gen(6974);
// double reqs[] = {15.1, 51.1, 94.9, 191.5, 246.3, 366.2, 490.3, 639.1,
// 731.4}; int i = 0; for (auto p : {0.001, 0.005256, 0.011546, 0.028545,
// 0.039856, 0.068648,
// 0.104571, 0.158765, 0.2}) {
// auto req = reqs[i++];
// exp_exist_query[1] = 0;
// exp_idk_query[1] = 1;
// exp_query[1] = 0, exp_chunk[1] = 1;
// for (int i = 2; i < 1001; ++i) {
// exp_exist_query[i] = 999999;
// exp_idk_query[i] = 999999;
// for (int k = 1; k < i; ++k) {
// // exp_exist
// double does_exist_prob = (1 - pow(1 - p, k)) / (1 - pow(1 - p, i));
// upd(exp_exist_query[i], exp_exist_chunk[i],
// 1 + does_exist_prob * (exp_exist_query[k] + exp_idk_query[i - k])
// +
// (1 - does_exist_prob) * exp_exist_query[i - k],
// k);
// // exp_idk
// does_exist_prob = 1 - pow(1 - p, k);
// upd(exp_idk_query[i], exp_idk_chunk[i],
// 1 + does_exist_prob * exp_exist_query[k] + exp_idk_query[i - k],
// k);
// // pick k randomly -> discard upon zero
// // if (pow(1 - p, -k) <= 10)
// // exp_idk_query[i] =
// // min(exp_idk_query[i], pow(1 - p, -k) + exp_idk_query[i -
// // k]);
// }
// if (exp_idk_query[i] > 1 + (1 - pow(1 - p, i)) * exp_exist_query[i]) {
// exp_idk_query[i] = 1 + (1 - pow(1 - p, i)) * exp_exist_query[i];
// did_check_all[i] = true;
// } else {
// did_check_all[i] = false;
// }
// }
// cout << fixed << setprecision(3) << p << ":\t" << req << "\t"
// << exp_idk_query[n] << "\t" << endl;
// // << req / (req + 4 * max(exp_idk_query[n] - req, 0.)) * 90 << endl;
// // 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;
// // }
// uniform_real_distribution<double> distrib(0, 1);
// int tot_q = 0;
// const int tests = 100;
// for (int t = 0; t < tests; ++t) {
// ans = string(n, '0');
// qcnt = 0;
// for (int i = 0; i < ans.size(); ++i)
// if (distrib(gen) < p) ans[i] = '1';
// ill = string(n, '0');
// vector<int> arr(n);
// iota(arr.begin(), arr.end(), 0);
// while (!arr.empty()) {
// // shuffle arr
// for (int i = arr.size() - 1; i > 0; --i)
// swap(arr[i], arr[gen() % (i + 1)]);
// solve(arr);
// arr.clear();
// arr.swap(to_ask_next);
// }
// if (ill != ans) {
// cout << "WA\n";
// }
// tot_q += qcnt;
// }
// double avg_q = (double)tot_q / tests;
// cout << "res:\t" << req << "\t" << avg_q << "\t"
// << req / (req + 4 * max(avg_q - req, 0.)) * 90 << endl;
// }
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> p >> t;
if (t == 1) {
exp_exist_chunk.assign(1001, 1);
exp_idk_chunk.assign(1001, 1);
is_tc1 = true;
} else {
exp_exist_query[1] = 0;
exp_idk_query[1] = 1;
exp_query[1] = 0, exp_chunk[1] = 1;
for (int i = 2; i < 1001; ++i) {
exp_exist_query[i] = 999999;
exp_idk_query[i] = 999999;
for (int k = 1; k < i; ++k) {
// exp_exist
double does_exist_prob = (1 - pow(1 - p, k)) / (1 - pow(1 - p, i));
upd(exp_exist_query[i], exp_exist_chunk[i],
1 + does_exist_prob * (exp_exist_query[k] + exp_idk_query[i - k]) +
(1 - does_exist_prob) * exp_exist_query[i - k],
k);
// exp_idk
does_exist_prob = 1 - pow(1 - p, k);
upd(exp_idk_query[i], exp_idk_chunk[i],
1 + does_exist_prob * exp_exist_query[k] + exp_idk_query[i - k], k);
}
if (exp_idk_query[i] > 1 + (1 - pow(1 - p, i)) * exp_exist_query[i]) {
exp_idk_query[i] = 1 + (1 - pow(1 - p, i)) * exp_exist_query[i];
did_check_all[i] = true;
} else {
did_check_all[i] = false;
}
}
}
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3672 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3928 KB |
Output is correct |
| 3 |
Correct |
7 ms |
3664 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 5 |
Correct |
8 ms |
3672 KB |
Output is correct |
| 6 |
Correct |
9 ms |
3672 KB |
Output is correct |
| 7 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 8 |
Correct |
8 ms |
3648 KB |
Output is correct |
| 9 |
Correct |
7 ms |
3724 KB |
Output is correct |
| 10 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 11 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 12 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 13 |
Correct |
10 ms |
3860 KB |
Output is correct |
| 14 |
Correct |
9 ms |
3928 KB |
Output is correct |
| 15 |
Correct |
8 ms |
3928 KB |
Output is correct |
| 16 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 17 |
Correct |
6 ms |
3672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
344 KB |
Output is correct (P=0.001, F=15.1, Q=13.2) -> 90.00 points |
| 2 |
Correct |
150 ms |
344 KB |
Output is correct (P=0.005256, F=51.1, Q=56.0) -> 65.05 points |
| 3 |
Correct |
246 ms |
460 KB |
Output is correct (P=0.011546, F=94.9, Q=106.7) -> 60.11 points |
| 4 |
Correct |
508 ms |
500 KB |
Output is correct (P=0.028545, F=191.5, Q=214.1) -> 61.14 points |
| 5 |
Correct |
667 ms |
496 KB |
Output is correct (P=0.039856, F=246.3, Q=274.0) -> 62.08 points |
| 6 |
Correct |
975 ms |
508 KB |
Output is correct (P=0.068648, F=366.2, Q=399.4) -> 66.05 points |
| 7 |
Correct |
1242 ms |
592 KB |
Output is correct (P=0.104571, F=490.3, Q=522.6) -> 71.23 points |
| 8 |
Correct |
1594 ms |
592 KB |
Output is correct (P=0.158765, F=639.1, Q=664.9) -> 77.49 points |
| 9 |
Correct |
1992 ms |
512 KB |
Output is correct (P=0.2, F=731.4, Q=751.4) -> 81.13 points |
