Submission #1237475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237475		Gray	COVID tests (CEOI24_covid)	C++20	10 / 100	7062 ms	436 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 get(ll l, ll r, vector<bool> &res){
    if (l==r){
        res[perm[l]]=1; return;
    }
    ll m = (l+r)/2;
    if (ask(l, m)) get(l, m, res);
    if (m+1<=r and ask(m+1, r)) get(m+1, r, res);
}

vector<bool> solvep(){
    vector<bool> res(n);
    get(0, n-1, res);
    return res;
}

void solve(){
    #ifdef LOCAL
    cin >> __res;
    #endif
    vector<bool> res = solvep();
    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: 10 / 10
• Subtask 2: 0 / 90