Submission #1219385

#TimeUsernameProblemLanguageResultExecution timeMemory
1219385j_vdd16COVID tests (CEOI24_covid)C++20
97.70 / 100
1153 ms636 KiB
#include <cassert> #include <cstdio> #include <string> #include <vector> #include <math.h> #include <iostream> #include <random> using namespace std; /// You may use: // The number of students int N; // The probability any given student is positive double P; vector<pair<double, int>> f, g; int solve(std::vector<bool>& result, int l, int r, bool containsPositive); bool bruteforce = false; int queryCount = 0; vector<bool> answers; void testAll(int num) { bruteforce = true; std::random_device rd; std::mt19937 gen(rd()); std::bernoulli_distribution d(P); answers.assign(N, false); queryCount = 0; for (int i = 0; i < num; i++) { for (int j = 0; j < N; j++) { answers[j] = d(gen); } std::vector<bool> answer(N); solve(answer, 0, N, false); if (i % (num / 100) == 0) { cout << g[N].first << " "; cout << double(queryCount) / double(i + 1) << endl; } } bruteforce = false; } // This function performs a test on a subset of samples. // Its argument is a vector of Booleans of length N, // where the i-th element is true if the i-th sample should be added to the mix. // It returns true if (and only if) at least one of the samples in the mix is positive. bool test_students(const std::vector<bool>& mask) { assert(mask.size() == (size_t)N); if (bruteforce) { queryCount++; for (int i = 0; i < N; i++) if (mask[i] && answers[i]) return true; return false; } std::string mask_str(N, ' '); for (int i = 0; i < N; i++) mask_str[i] = mask[i] ? '1' : '0'; printf("Q %s\n", mask_str.c_str()); fflush(stdout); char answer; scanf(" %c", &answer); return answer == 'P'; } /* f(n) = argmin( (f(k) + g(n - k)) * (k / n + (n - k) / n * (1 - (1 - P)^k)) + ) */ void init() { f.assign(N + 1, {100000.0, -1}); g.assign(N + 1, {100000.0, -1}); f[0] = {0, 0}; f[1] = {0, 0}; g[0] = {0, 0}; g[1] = {1, 1}; vector<double> pw(N + 1); for (int i = 0; i <= N; i++) pw[i] = pow(1.0 - P, i); for (int n = 2; n <= N; n++) { for (int k = 1; k < n; k++) { double p = (1.0 - pw[k]) / (1 - pw[n]);//double(k) / double(n) + double(n - k) / double(n) * (1.0 - pw[k]); double exp = 1.0 + p * (f[k].first + g[n - k].first) + (1 - p) * (f[n - k].first); if (exp < f[n].first) { f[n] = {exp, k}; } } for (int k = 1; k <= n; k++) { double p = 1.0 - pw[k]; double exp = 1.0 + p * (f[k].first + g[n - k].first) + (1 - p) * (g[n - k].first); if (exp < g[n].first) { g[n] = {exp, k}; } } } } /* 1100010010 0001 */ int solve(std::vector<bool>& result, int l, int r, bool containsPositive) { int n = r - l; if (n == 0) return -1; if (containsPositive && n == 1) { result[l] = true; return l; } int k = containsPositive ? f[n].second : g[n].second; vector<bool> mask(N); for (int i = l; i < l + k; i++) mask[i] = true; bool res = test_students(mask); if (containsPositive) { if (res) return solve(result, l, l + k, true); else return solve(result, l + k, r, true); } else { if (res) { int firstPositive = solve(result, l, l + k, true); return solve(result, firstPositive + 1, r, false); } else { return solve(result, l + k, r, false); } } } std::vector<bool> find_positive() { init(); //testAll(1000); std::vector<bool> answer(N); //return answer; if (P == 0.0) return answer; if (P == 1.0) { for (int i = 0; i < N; i++) answer[i] = true; return answer; } //cerr << g[N].first << endl; solve(answer, 0, N, false); return answer; } int main() { int T; scanf("%d %lf %d", &N, &P, &T); // You may perform any extra initialization here. for (int i = 0; i < T; i++) { std::vector<bool> answer = find_positive(); assert(answer.size() == (size_t)N); std::string answer_str(N, ' '); for (int j = 0; j < N; j++) answer_str[j] = answer[j] ? '1' : '0'; printf("A %s\n", answer_str.c_str()); fflush(stdout); char verdict; scanf(" %c", &verdict); if (verdict == 'W') exit(0); } return 0; }

Compilation message (stderr)

Main.cpp: In function 'bool test_students(const std::vector<bool>&)':
Main.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf(" %c", &answer);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:191:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |     scanf("%d %lf %d", &N, &P, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:207:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |         scanf(" %c", &verdict);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...