Submission #1196471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196471		Turkhuu	COVID tests (CEOI24_covid)	C++20	49.79 / 100	674 ms	408 KiB

Main

#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
int n, t;
double P;
int qry(string s) {
    cout << "Q " << s << endl;
    char c;
    cin >> c;
    return c == 'P';
}
int qry(int l, int r) {
    string s(n, '0');
    FOR(i, l, r) s[i] = '1';
    return qry(s);
}
void answer(string s) {
    cout << "A " << s << endl;
    char c;
    cin >> c;
    if (c == 'W') exit(0);
}
string solve1(int x) {
    string ans(n, '0');
    for (int i = 0; i < n; i += x) {
        if (qry(i, min(n - 1, i + x - 1))) {
            int f = 0;
            for (int j = i; j < min(n, i + x); j++) {
                if (!f && j + 1 == min(n, i + x)) ans[j] = '1';
                else if (qry(j, j)) ans[j] = '1', f = 1;
            }
        }
    }
    return ans;
}
string solve2(int x) {
    string ans(n, '0');
    for (int i = 0; i < n;) {
        int j = min(n - 1, i + x - 1);
        if (!qry(i, j)) {i = j + 1; continue;}
        for (int k = i, lo = i, hi = j + 1; k <= j; k = ++lo, hi = j + 1) {
            while (lo < hi) {
                int mi = (lo + hi) / 2;
                qry(k, mi) ? hi = mi : lo = mi + 1;
            }
            if (lo <= j) ans[lo] = '1';
        }
        i = j + 1;
    }
    return ans;
}
void bodooroi() {
    string ans(n, '0');
    if (t == 1) {
        ans = solve1(1);
    } else if (1) {
        ans = solve2(1 / P / 2);
    } else if (P == 0.2) {
        ans = solve1(3);
    } else if (P >= 0.1) {
        ans = solve1(2);
    } else if (P >= 0.15) {
        FOR(i, 0, n - 1) if (qry(i, i)) ans[i] = '1';
    } else {
        for (int i = 0, lo = 0, hi = n; i < n; i = ++lo, hi = n) {
            while (lo < hi) {
                int mi = (lo + hi) / 2;
                qry(i, mi) ? hi = mi : lo = mi + 1;
            }
            if (lo < n) ans[lo] = '1';
        }
    }
    answer(ans);    
}
int main() {
    cin >> n >> P >> t;
    for (int i = t; i--; bodooroi());
    return 6/22;
}

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