oj.uz

답안 #1034956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1034956 2024-07-26T00:22:25 Z TAMREF COVID tests (CEOI24_covid) C++17
10 / 100
 7000 ms 612 KB 
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(), (v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
template <typename... Args>
void logger(string vars, Args &&...values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << '\n';
}
#ifdef TAMREF
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
#else
#define deb(...) 42
#endif
using ll = long long;
using lf = long double;
using pii = pair<int, int>;
using ppi = pair<int, pii>;
using pll = pair<ll, ll>;
using pff = pair<lf, lf>;
using ti = tuple<int, int, int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T &u, T v) { return u = max(u, v); }
template <typename T>
inline T umin(T &u, T v) { return u = min(u, v); }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> ans;

int n, t, qnt, lqnt, mqnt;
lf p;

int query(vector<int> F)
{
    ++qnt;
    ++lqnt;
    vector<int> A(n);
    for (int i : F)
    {
        A[i] = 1;
    }

    cout << "Q ";
    for (int x : A)
        cout << x;
    cout << endl;

    int q = 0;
#ifdef TAMREF
    for (int i : F)
        q = max(q, ans[i]);
#else
    string S;
    cin >> S;
    q = (S == "P");
#endif

    return q;
}

int query_seg(int i, int j)
{
    if (i > j)
        return 0;
    vector<int> f;
    for (int k = i; k <= j; k++)
        f.push_back(k);
    return query(f);
}

int query_seg(pii x)
{
    return query_seg(x.va, x.vb);
}

void answer(vector<int> F)
{
    mqnt = max(mqnt, lqnt);
    lqnt = 0;
    vector<int> A(n);
    for (int i : F)
        A[i] = 1;

    cout << "A ";
    for (int i : A)
        cout << i;
    cout << endl;

#ifdef TAMREF
    assert(ans == A);
#else
    string C;
    cin >> C;
    assert(C == "C");
#endif
}

vector<pii> initial_segs;
void init()
{
    if (t > 1 && initial_segs.empty()) {
        uniform_real_distribution st(100.0, 200.0);
        int step = 1;
        for (int i = 0; i < n; i += step)
        {
            step = max(300, int(st(rng) / p));

            initial_segs.emplace_back(i, min(n - 1, i + step - 1));
        }
    }
#ifdef TAMREF
    uniform_real_distribution<lf> d(0, 1);

    ans = vector<int>(n);
    for (int i = 0; i < n; i++)
        ans[i] = d(rng) < p;
#endif
}

void run_det()
{
    vector<int> ans;
    for (int i = 0; i < n; i++)
    {
        if (query(vector<int>({i})))
            ans.push_back(i);
    }

    answer(ans);
}

void run()
{
    uniform_real_distribution st(100.0, 200.0);
    vector<int> ans;

    deque<pii> segs;
    for(auto &v : initial_segs) {
        if(query_seg(v)) segs.emplace_back(v);
    }

    while (szz(segs))
    {
        pii sg = segs.front();
        segs.pop_front();

        if (sg.va == sg.vb)
        {
            ans.push_back(sg.va);
            continue;
        }

        if (sg.va + 1 == sg.vb)
        {
            if (query_seg(sg.va, sg.va))
            {
                ans.push_back(sg.va);
                if (query_seg(sg.vb, sg.vb))
                {
                    ans.push_back(sg.vb);
                }
            }
            else
            {
                ans.push_back(sg.vb);
            }
            continue;
        }

        int m = (sg.vb - sg.va + 1) / 2;
        pii lsg(sg.va, sg.va + m - 1), rsg(sg.va + m, sg.vb);

        if (lsg.va <= lsg.vb && query_seg(lsg))
        {
            segs.push_back(lsg);

            if (rsg.va <= rsg.vb && query_seg(rsg))
            {
                segs.push_back(rsg);
            }
        }
        else
        {
            if (rsg.va <= rsg.vb)
            {
                segs.push_back(rsg);
            }
        }
    }

    answer(ans);
}

int main()
{
    cin >> n >> p >> t;

    if (t == 1)
    {
        init();
        run_det();
    }
    else
    {
        for (int j = 0; j < t; j++)
        {
            init();
            run();
        }
        debug("average query: %.3Lf\n", lf(qnt) / t);
        debug("max query: %d\n", mqnt);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:319:9: note: in expansion of macro 'debug'
  319 |         debug("average query: %.3Lf\n", lf(qnt) / t);
      |         ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:320:9: note: in expansion of macro 'debug'
  320 |         debug("max query: %d\n", mqnt);
      |         ^~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 344 KB Output is correct
2 Correct 35 ms 344 KB Output is correct
3 Correct 38 ms 592 KB Output is correct
4 Correct 62 ms 344 KB Output is correct
5 Correct 35 ms 436 KB Output is correct
6 Correct 61 ms 344 KB Output is correct
7 Correct 36 ms 592 KB Output is correct
8 Correct 42 ms 344 KB Output is correct
9 Correct 36 ms 344 KB Output is correct
10 Correct 52 ms 344 KB Output is correct
11 Correct 36 ms 344 KB Output is correct
12 Correct 53 ms 344 KB Output is correct
13 Correct 45 ms 344 KB Output is correct
14 Correct 58 ms 344 KB Output is correct
15 Correct 37 ms 344 KB Output is correct
16 Correct 48 ms 596 KB Output is correct
17 Correct 36 ms 344 KB Output is correct

Subtask #2
0.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 344 KB Output is correct (P=0.001, F=15.1, Q=13.8) -> 90.00 points
2 Correct 767 ms 344 KB Output is correct (P=0.005256, F=51.1, Q=60.7) -> 51.39 points
3 Correct 1408 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=117.9) -> 45.70 points
4 Correct 2834 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=240.7) -> 44.39 points
5 Correct 3523 ms 612 KB Output is correct (P=0.039856, F=246.3, Q=309.4) -> 44.45 points
6 Correct 4648 ms 452 KB Output is correct (P=0.068648, F=366.2, Q=458.3) -> 44.87 points
7 Execution timed out 7022 ms 592 KB Time limit exceeded
8 Halted 0 ms 0 KB -