Submission #1214044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214044		I_am_Polish_Girl	COVID tests (CEOI24_covid)	C++20	10 / 100	36 ms	788 KiB

Main

#pragma GCC optimize "Ofast"

//In honor of TimDee

/*
In honor of Anton Tsypko
I want earrings with minecreaft
I want earrings with birbie
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <string>
#include <queue>
#include <random>
#include <chrono>
#include <unordered_map>
#include <stack>
#include <bitset>


using namespace std;


//#include "fish.h"

#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <bitset>
#include <cmath>
#include <string>

using namespace std;

#define int long long

long long inf = 1000000000000000000;
int log_ = 18;
int mod = 1000000007;
int p = 803;


int N = 100000;


int sq = 350;


int n, times;

double per;
map<int, int> mp;


int hs(vector <int> a)
{
    int h = 0;
    for (int i = 0; i < a.size(); i++)
    {
        h *= p;
        h += a[i];

        h %= mod;
    }

    return h;
}

int q(vector <int> a)
{

    if (mp.count(hs(a)) != 0)
    {
        return mp[hs(a)];
    }

    string s;
    s.resize(a.size());

    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == 0)
            s[i] = '0';
        else
            s[i] = '1';
    }

    cout << "Q " << s << endl;

    char ch;

    cin >> ch;

    int r = 1;

    if (ch == 'P')
        r = 1;
    else
        r = 0;

    mp[hs(a)] = r;

    if (ch == 'P')
        return 1;
    else
        return 0;
}



void answer(vector <int> a)
{
    string s;
    s.resize(a.size());

    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == 0)
            s[i] = '0';
        else
            s[i] = '1';
    }


    cout << "A " << s << endl;

    char ch;

    cin >> ch;
}



vector <int> ans;


void rec(int l, int r)
{
    if (l >= r)
        return;


    vector <int> a(n);

    for (int i = l; i < r; i++)
    {
        a[i] = 1;
    }


    if (l + 1 == r)
    {

        if (q(a) == 1)
            ans[l] = 1;
        return;
    }

    int m = (l + r) / 2;

    if (q(a) == 1)
    {

        vector <int> a1(n);

        for (int i = l; i < m; i++)
        {
            a1[i] = 1;
        }


        vector <int> a2(n);

        for (int i = m; i < r; i++)
        {
            a2[i] = 1;
        }

        rec(l, m);
        rec(m, r);
    }

    return;
}


mt19937 rnd(12);

int rnd_(int x)
{
    int a = rnd();

    a = abs(a);
    a %= x;

    return a;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);


    cin >> n >> per >> times;

    while (times--)
    {
        ans.clear();
        ans.resize(n);

        int bl = n;
        int lx = 0;

        if (bl < 1)
            bl = 1;

        rec(0, n);

        answer(ans);
    }
}

/*
5 11
0 1 1
0 2 1
0 3 1
0 4 1
0 0 1
2 0 1
2 1 1
2 2 1
2 3 1
2 4 1
4 4 1

*/

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