Submission #1075369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075369		Ausp3x	COVID tests (CEOI24_covid)	C++17	40.85 / 100	7068 ms	596 KiB

Main

// 人外有人，天外有天
// author: Ausp3x

#pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
// #define DEBUG
typedef long long    lng;
typedef __int128     lli;
template<class T> 
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;

int N, T;
double P;

bool test_students(vector<bool> &msk) {
    assert(msk.size() == N);

    string msk_str = "Q ";
    for (int i = 0; i < N; i++)
        msk_str += msk[i] ? '1' : '0';

    cout << msk_str << endl;

    char res;
    cin >> res;
    return res == 'P';
}

/* bible generator (it lied)
Es = [1, 5, 12, 29, 40, 69, 105, 159, 200]

S = '{'
for E in Es:
    S += '\n{'
    S += f'{E}'
    S += ', {'
    for i in range(0, 1001):
        if i <= E:
            S += '0, '
            continue
            
        cnt = 0  
        cur_prob = 1  
        prob_N = (1 - E / i)
        while cur_prob * prob_N >= 0.5:
            cnt += 1
            cur_prob *= prob_N
        
        S += f'{cnt}, '
    
    S = S[:-2]        
    S += '}}, '
              
S = S[:-2]
S += '\n}'

print(S)
//*/

vector<bool> msk, ans;
vector<int> to_test;

void binarySearch(int l, int r) {
    if (l > r)
        return;
    
    // cout << l << ' ' << r << endl;

    if (l == r) {
        msk[to_test[l]] = true;
        bool res = test_students(msk);
        msk[to_test[l]] = false;

        ans[to_test[l]] = res;
        
        return;
    }

    int md = (l + r) / 2;

    for (int i = l; i <= md; i++) 
        msk[to_test[i]] = true;
    bool l_res = test_students(msk);
    for (int i = l; i <= md; i++) 
        msk[to_test[i]] = false;

    for (int i = md + 1; i <= r; i++)
        msk[to_test[i]] = true;
    bool r_res = test_students(msk);
    for (int i = md + 1; i <= r; i++)
        msk[to_test[i]] = false;
    
    if (md - l + 1 == 1) {
        ans[to_test[l]] = l_res;
    } else {
        if (l_res)
            binarySearch(l, md);
    }

    if (r - md == 1) {
        ans[to_test[r]] = r_res;   
    } else {
        if (r_res)
            binarySearch(md + 1, r);
    }

    return;
}

vector<bool> find_positive() {
    if (T == 1) {
        msk.clear();
        msk.resize(N);
        ans.clear();
        ans.resize(N);
        for (int i = 0; i < N; i++) {
            msk[i] = true;
            ans[i] = test_students(msk);
            msk[i] = false;
        }
        
        return ans;
    }

    double err = 1e-9;
    int R = 0;
    if (abs(P - 0.001) <= err) {
        R = 1000;
    } else if (abs(P - 0.005256) <= err) {
        R = 160;
    } else if (abs(P - 0.011546) <= err) {
        R = 80;
    } else if (abs(P - 0.028545) <= err) {
        R = 40; 
    } else if (abs(P - 0.039856) <= err) {
        R = 20;
    } else if (abs(P - 0.068648) <= err) {
        R = 10;
    } else if (abs(P - 0.104571) <= err) {
        R = 8;
    } else if (abs(P - 0.158765) <= err) {
        R = 8;
    } else if (abs(P - 0.2) <= err) {
        R = 4;
    }

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
    msk.clear();
    msk.resize(N);
    ans.clear();
    ans.resize(N);
    to_test.clear();
    to_test.resize(N);
    iota(to_test.begin(), to_test.end(), 0);
    shuffle(to_test.begin(), to_test.end(), rng);
    
    for (int i = 0; i < N; i += R)
        binarySearch(i, min(i + R - 1, N - 1));

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> P >> T;
    for (int _ = 0; _ < T; _++) {
        vector<bool> ans = find_positive();

        assert(ans.size() == N);

        string ans_str = "A ";
        for (int i = 0; i < N; i++)
            ans_str += ans[i] ? '1' : '0';

        cout << ans_str << endl;

        char res;
        cin >> res;
        if (res == 'W')
            return 0;
    }

    return 0;
}

Compilation message (stderr)

Main.cpp:4:55: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
      |                                                       ^
Main.cpp:4:55: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
Main.cpp:4:55: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
Main.cpp:4:55: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
Main.cpp:25:37: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   25 | bool test_students(vector<bool> &msk) {
      |                                     ^
Main.cpp:25:37: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
Main.cpp:25:37: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:25:37: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from Main.cpp:6:
Main.cpp: In function 'bool test_students(std::vector<bool>&)':
Main.cpp:26:23: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |     assert(msk.size() == N);
      |            ~~~~~~~~~~~^~~~
Main.cpp: At global scope:
Main.cpp:73:31: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   73 | void binarySearch(int l, int r) {
      |                               ^
Main.cpp:73:31: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
Main.cpp:73:31: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:73:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:120:28: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  120 | vector<bool> find_positive() {
      |                            ^
Main.cpp:120:28: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
Main.cpp:120:28: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:120:28: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:174:10: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  174 | int main() {
      |          ^
Main.cpp:174:10: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
Main.cpp:174:10: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:174:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from Main.cpp:6:
Main.cpp: In function 'int main()':
Main.cpp:182:27: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  182 |         assert(ans.size() == N);
      |                ~~~~~~~~~~~^~~~

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