| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1026699 |
2024-07-18T09:23:21 Z |
우민규(#10946) |
COVID tests (CEOI24_covid) |
C++17 |
|
74 ms |
344 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;
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 (!certain_exists)
to_ask_next.insert(to_ask_next.end(), candidate.begin(), candidate.end());
if (ask(cur)) {
solve(next_candidate, true);
if (certain_exists) solve(candidate, false);
} else {
if (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);
// 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';
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);
} 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;
}
Compilation message
Main.cpp: In function 'bool ask(std::string&)':
Main.cpp:17:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i = 0; i < ans.size(); ++i)
| ~~^~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:148:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for (int i = 0; i < ans.size(); ++i)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
74 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
344 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
