제출 #1183414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183414		gyg	COVID tests (CEOI24_covid)	C++20	66.30 / 100	1275 ms	480 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) {
    return 1 - powl(1 - p, 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 a = (doub) i / x * (dp[i][1].fir + dp[x - i][0].fir + 1);
            doub b = (doub) (x - i) / x * (prb(i) * dp[i][1].fir + dp[x - i][1].fir + 1);
            dp[x][1] = min(dp[x][1], {a + b, i});
        }

        dp[x][0] = {prb(x) * dp[x][1].fir + 1, x};
        for (int i = 1; i < x; i++) {
            doub a = prb(i) * dp[i][1].fir + dp[x - i][0].fir + 1;
            dp[x][0] = min(dp[x][0], {a, 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;
    }
}

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