| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1026622 |
2024-07-18T08:43:44 Z |
우민규(#10946) |
COVID tests (CEOI24_covid) |
C++17 |
|
1641 ms |
3784 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);
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 (ask(cur)) {
solve(next_candidate, true);
solve(candidate, false);
} else {
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);
solve(candidates);
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';
// vector<int> arr(n);
// iota(arr.begin(), arr.end(), 0);
// if (ans != string(n, '0')) {
// int x = 3;
// }
// ill = string(n, '0');
// solve(arr);
// 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);
} 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 |
9 ms |
3660 KB |
Output is correct |
| 3 |
Correct |
7 ms |
3672 KB |
Output is correct |
| 4 |
Correct |
7 ms |
3784 KB |
Output is correct |
| 5 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 6 |
Correct |
6 ms |
3652 KB |
Output is correct |
| 7 |
Correct |
7 ms |
3480 KB |
Output is correct |
| 8 |
Correct |
6 ms |
3684 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3416 KB |
Output is correct |
| 10 |
Correct |
6 ms |
3416 KB |
Output is correct |
| 11 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 12 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 13 |
Correct |
8 ms |
3656 KB |
Output is correct |
| 14 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 15 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 16 |
Correct |
6 ms |
3560 KB |
Output is correct |
| 17 |
Correct |
9 ms |
3672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
740 KB |
Output is correct (P=0.001, F=15.1, Q=13.2) -> 90.00 points |
| 2 |
Correct |
130 ms |
520 KB |
Output is correct (P=0.005256, F=51.1, Q=56.0) -> 65.05 points |
| 3 |
Correct |
214 ms |
556 KB |
Output is correct (P=0.011546, F=94.9, Q=106.6) -> 60.28 points |
| 4 |
Correct |
471 ms |
896 KB |
Output is correct (P=0.028545, F=191.5, Q=214.3) -> 60.97 points |
| 5 |
Correct |
557 ms |
896 KB |
Output is correct (P=0.039856, F=246.3, Q=273.6) -> 62.35 points |
| 6 |
Correct |
827 ms |
888 KB |
Output is correct (P=0.068648, F=366.2, Q=399.0) -> 66.26 points |
| 7 |
Correct |
938 ms |
876 KB |
Output is correct (P=0.104571, F=490.3, Q=522.8) -> 71.14 points |
| 8 |
Correct |
1375 ms |
1360 KB |
Output is correct (P=0.158765, F=639.1, Q=663.6) -> 78.03 points |
| 9 |
Correct |
1641 ms |
1544 KB |
Output is correct (P=0.2, F=731.4, Q=750.4) -> 81.53 points |
