Submission #1285817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285817		AksLolCoding	COVID tests (CEOI24_covid)	C++17	100 / 100	543 ms	332 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}

mt19937 rng(5495825);
const double EPS = 1e-6;
const int MN = 1005;
int t, n, q;
double p;
bool actAns[MN], ans[MN];

bool query(int l, int r){
    q++;
    #ifdef LOCAL
        return *max_element(actAns+l, actAns+r);
    #else
        string str(n, '0');
        FOR(i, l, r) str[i] = '1';
        cout << "Q " << str << endl;
        char res; cin >> res;
        return res == 'P';
    #endif
}

void printAns(){
    #ifndef LOCAL
        cout << "A ";
        FR(i, n) cout << ans[i];
        cout << endl;
        char res; cin >> res;
        assert(res == 'C');
    #endif
}

void solve(){
    ms(ans, 0);
    if(p == 0){printAns(); return;}
    if(p == 1){ms(ans, 1); printAns(); return;}
    FR(i, n) actAns[i] = uniform_real_distribution(0.0, 1.0)(rng) < p;

    int ind = 0;
    int bsz = 1/p + 0.1;

    if(abs(0.2 - p) <= EPS) bsz = 3;
    if(abs(0.158765 - p) <= EPS) bsz = 4;
    if(abs(0.104571 - p) <= EPS) bsz = 7;
    if(abs(0.068648 - p) <= EPS) bsz = 8;
    if(abs(0.039856 - p) <= EPS) bsz = 16;
    if(abs(0.028545 - p) <= EPS) bsz = 32;

    while(ind < n){
        int r = min(ind+bsz, n);
        if(!query(ind, r)){ind = r; continue;}

        int lo = ind, hi = r-1;
        while(lo < hi){
            int mid = (lo+hi-1)/2;
            if(query(lo, mid+1)) hi = mid;
            else lo = mid+1;
        }
        ans[lo] = true;
        ind = lo+1;
    }

    printAns();
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n >> p >> t;
    FR(ti, t) solve();
    dbg(q/t);
}

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