제출 #1034334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034334		TAMREF	COVID tests (CEOI24_covid)	C++17	10 / 100	7067 ms	5156 KiB

Main

// 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;
lf p;

int query(vector<int> F)
{
    ++qnt;
    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;
}

void answer(vector<int> F)
{
    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
}

void init()
{
    #ifdef TAMREF
    uniform_real_distribution<lf> d(0, 1);

    ans = vector<int>(n);
    for (int i = 0; i < n; i++)
        ans[i] = d(rng);
    #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(5.0, 20.0);
    vector<int> ans;

    deque<vector<int>> segs;
    int step = 1;
    for (int i = 0; i < n; i += step)
    {
        step = max(2, int(st(rng) / p));
        vector<int> seg;
        for (int j = i; j < n && j < i + step; j++)
            seg.push_back(j);

        if (query(seg))
            segs.push_back(seg);
    }

    while(szz(segs))
    {
        vector<int> sg = segs.front();
        segs.pop_front();

        if (szz(sg) == 1)
            ans.push_back(sg[0]);

        int m = szz(sg) / 2;
        vector<int> lsg(sg.begin(), sg.begin() + m),
            rsg(sg.begin() + m, sg.end());

        if (query(lsg))
        {
            segs.push_back(lsg);

            if (query(rsg))
            {
                segs.push_back(rsg);
            }
        }
        else
        {
            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);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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