oj.uz

Submission #1075374

# Submission time Handle Problem Language Result Execution time Memory
1075374 2024-08-26T04:45:35 Z Ausp3x COVID tests (CEOI24_covid) C++17
40.11 / 100
 5656 ms 344 KB 
// 人外有人，天外有天
// 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 = 32; 
    } else if (abs(P - 0.039856) <= err) {
        R = 24;
    } else if (abs(P - 0.068648) <= err) {
        R = 12;
    } else if (abs(P - 0.104571) <= err) {
        R = 8;
    } else if (abs(P - 0.158765) <= err) {
        R = 6;
    } 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) {
        int l = i, r = min(i + R - 1, N - 1);
        
        for (int i = l; i <= r; i++)
            msk[to_test[i]] = true;
        bool res = test_students(msk);
        for (int i = l; i <= r; i++) 
            msk[to_test[i]] = false;

        if (!res)
            continue;

        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

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:186:10: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  186 | int main() {
      |          ^
Main.cpp:186:10: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
Main.cpp:186:10: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:186: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:194:27: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  194 |         assert(ans.size() == N);
      |                ~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5656 ms 344 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 7 ms 344 KB Output is correct
8 Correct 7 ms 344 KB Output is correct
9 Correct 8 ms 344 KB Output is correct
10 Correct 7 ms 344 KB Output is correct
11 Correct 10 ms 344 KB Output is correct
12 Correct 7 ms 344 KB Output is correct
13 Correct 7 ms 344 KB Output is correct
14 Correct 10 ms 344 KB Output is correct
15 Correct 7 ms 344 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 7 ms 344 KB Output is correct

Subtask #2
30.110000004 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 344 KB Output is correct (P=0.001, F=15.1, Q=17.8) -> 52.47 points
2 Correct 227 ms 340 KB Output is correct (P=0.005256, F=51.1, Q=75.0) -> 31.35 points
3 Correct 402 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=142.1) -> 30.11 points
4 Correct 784 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=277.4) -> 32.21 points
5 Correct 998 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=358.4) -> 31.91 points
6 Correct 1405 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=513.4) -> 34.51 points
7 Correct 1874 ms 344 KB Output is correct (P=0.104571, F=490.3, Q=648.9) -> 39.23 points
8 Correct 2380 ms 344 KB Output is correct (P=0.158765, F=639.1, Q=844.7) -> 39.36 points
9 Correct 2529 ms 344 KB Output is correct (P=0.2, F=731.4, Q=907.1) -> 45.90 points