Submission #1183443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183443		gyg	COVID tests (CEOI24_covid)	C++20	0 / 100	2 ms	436 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define doub long double
#define arr array
#define vec vector 
#define fir first 
#define sec second
const int N = 1e3 + 5, INF = 1e12;

int n;
doub p;

bool qry(int l, int r) {
    string ans = "";
    for (int i = 1; i <= n; i++)
        ans += (l <= i && i <= r) ? "1" : "0";
    cout << "Q " << ans << endl;
    
    char x; cin >> x;
    return (x == 'P');
}

doub prb(int x, doub e) {
    return 1 - powl(1 - e, x);
}

arr<arr<pair<doub, int>, 2>, N> dp;
void dp_cmp() {
    dp[0][0] = {0, -1}, dp[0][1] = {INF, -1};
    dp[1][0] = {1, 1}, dp[1][1] = {0, -1};

    for (int x = 2; x <= n; x++) {
        dp[x][1] = {INF, -1};
        for (int i = 1; i < x; i++) {
            doub prb_a = i / (doub) x + prb(x - i, p);
            doub a = dp[i][1].fir + dp[x - i][0].fir + 1;

            doub prb_b = 1 - prb_a;
            doub b = dp[x - i][1].fir + 1;

            dp[x][1] = min(dp[x][1], {prb_a * a + prb_b * b, i});
        }

        dp[x][0] = {prb(x, p) * dp[x][1].fir + 1, x};
        for (int i = 1; i < x; i++) {
            doub prb_a = prb(i, p);
            doub a = dp[i][1].fir + dp[x - i][0].fir + 1;
            
            doub prb_b = 1 - prb_a;
            doub b = dp[x - i][0].fir + 1;

            dp[x][0] = min(dp[x][0], {prb_a * a + prb_b * b, i});
        }

        // cout << x << ": " << dp[x][0].fir << " " << dp[x][1].fir << '\n';
    }
}

arr<bool, N> on;
void slv(int l = 1, int r = n, int b = 0) {
    if (l > r) return;
    int x = r - l + 1;
    int i = dp[x][b].sec;
    if (i == -1) { on[l] = true; return;}
    i = l + i - 1;

    if (qry(l, i)) {
        slv(l, i, 1);
        slv(i + 1, r, 0);
    } else {
        if (b == 0) slv(i + 1, r, 0);
        else slv(i + 1, r, 1);
    }
}

signed main() {
    freopen("in", "r", stdin);
    int x; cin >> n >> p >> x;
    dp_cmp();
    for (int i = 1; i <= x; i++) {
        on.fill(false);
        slv();

        string ans = "";
        for (int j = 1; j <= n; j++)
            ans += (on[j] ? "1" : "0");
        cout << "A " << ans << endl;

        char y; cin >> y;
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     freopen("in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 90