Submission #1237487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237487		Gray	COVID tests (CEOI24_covid)	C++20	0 / 100	456 ms	452 KiB

Main

#include<bits/stdc++.h>
#define ld long double
#define ll long long
#define ff first
#define ss second
#define ln "\n"

using namespace std;
const ll INF = 2e9;

ll n, t; ld p;
string __res;

bool test(vector<bool> &give){
    #ifndef LOCAL
    cout << "Q ";
    for (ll i=0; i<n; i++) cout << give[i];
    cout << endl;
    char x; cin >> x; return (x=='P');
    #else
    bool res=0;
    for (ll i=0; i<n; i++){
        if (give[i] and __res[i]-'0') res=1;
    }
    return res;
    #endif
}

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<ll> perm;
vector<bool> qry;
bool ask(ll l, ll r){
    for (ll i=l; i<=r; i++) qry[perm[i]]=1;
    bool ans=test(qry);
    for (ll i=l; i<=r; i++) qry[perm[i]]=0;
    return ans;
}



void solve(){
    #ifdef LOCAL
    cin >> __res;
    #endif
    vector<bool> res(n);
    ll cont = 1.0/p, avg = (ld)n*p+10;
    ll cur=0;
    while (avg){
        ll l=cur-1, r=min(n, cur+cont*10);
        while (l+1<r){
            ll mid = (l+r)/2;
            if (ask(cur, mid)) r=mid;
            else l=mid; 
        }
        if (r==n) break;
        res[perm[r]]=1; avg--; cur=r+1;
    }
    cout << "A ";
    for (ll i=0; i<n; i++) cout << res[i];
    cout << endl; char _; cin >> _;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> p >> t;
    perm.assign(n, 0); qry.assign(n, 0);
    for (ll i=0; i<n; i++) perm[i]=i;
    shuffle(perm.begin(), perm.end(), rnd);
    while (t--){
        solve();
    }
}

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