oj.uz

Submission #1035207

# Submission time Handle Problem Language Result Execution time Memory
1035207 2024-07-26T06:39:52 Z TAMREF COVID tests (CEOI24_covid) C++17
44.82 / 100
 1837 ms 344 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());
 
map<lf, lf> score = {
    {0.001, 15.1},
    {0.005256, 51.1},
    {0.011546, 94.9},
    {0.028545, 191.5},
    {0.039856, 246.3},
    {0.068648,
     366.2},
    {0.104571,
     490.3},
    {0.158765, 639.1},
    {0.2, 731.4}};
string ans;
 
int n, t, qnt, lqnt, mqnt;
lf p;
 
int query(string F)
{
    ++qnt;
    ++lqnt;
 
#ifndef TAMREF
    cout << "Q " << F << '\n';
    cout << flush;
#endif
 
    int q = 0;
#ifdef TAMREF
    for (int i = 0; i < n; i++)
        q |= (ans[i] == '1') && (F[i] == '1');
#else
    string S;
    cin >> S;
    q = (S == "P");
#endif
 
    return q;
}
 
int query_seg(int i, int j)
{
    debug("qseg %d %d\n", i, j);
    if (i > j)
        return 0;
 
    string f(n, '0');
    for (int k = i; k <= j; k++)
        f[k] = '1';
 
    return query(f);
}
 
int query_seg(pii x)
{
    return query_seg(x.va, x.vb);
}
 
void answer(string F)
{
    mqnt = max(mqnt, lqnt);
    lqnt = 0;
 
#ifndef TAMREF
    cout << "A " << F << '\n';
    cout << flush;
#endif
 
#ifdef TAMREF
    assert(ans == F);
#else
    string C;
    cin >> C;
    assert(C == "C");
#endif
}
 

lf dp[1005], dp2[1005];
lf pows[1005] = {1.0};
int opt[1005], opt2[1005];
vector<ti> initial_segs;
 
void init()
{
    if (t > 1 && initial_segs.empty())
    {
        for (int i = 1; i <= n; i++)
            pows[i] = pow(1.0L - p, i);
 
        for (int i = 2; i <= n; i++)
        {
            dp[i] = 10.L * i;
            dp2[i] = 10.L * i;

            // know
            for(int j = 1; j < i; j++) {
                lf pdp = pows[j] * (1.L - pows[i-j]) / (1.L - pows[i]) * (1.L + dp2[i-j]) + (1.L - pows[j]) / (1.L - pows[i]) * (1.L + dp2[j] + dp[i-j]);
                if(pdp < dp2[i]) {
                    dp2[i] = pdp;
                    opt2[i] = j;
                }
            }

            // don't know
            for(int j = 1; j <= i; j++) {
                // dp[i] * q^i
                lf pdp = pows[j] * (1.L + dp[i-j]) + (1.L - pows[j]) * (1.L + dp2[j] + dp[i-j]);
                if (pdp < dp[i]) {
                    dp[i] = pdp;
                    opt[i] = j;
                }
            }
        }

        for(int i = 0; i <= n; i++) debug("pows[%d] = %.6Lf\n", i, pows[i]);
        for(int i = 1; i <= n; i++) {
            debug("dp[%d] = %.3Lf (opt=%d), dp2[%d] = %.3Lf (opt2=%d)\n", i, dp[i], opt[i], i, dp2[i], opt2[i]);
        }
        debug("dp[%d] = %.3Le\n", n, dp[n]);

        initial_segs.emplace_back(0, n-1, 0);
    }
#ifdef TAMREF
    uniform_real_distribution<lf> d(0, 1);
 
    ans = string(n, '0');
 
    for (int i = 0; i < n; i++)
        ans[i] = (d(rng) < p ? '1' : '0');
#endif
}
 
void run_det()
{
    string ans(n, '0');
    for (int i = 0; i < n; i++)
    {
        if (query_seg(i, i))
            ans[i] = '1';
    }
 
    answer(ans);
}
 
void run()
{
    debug("================\n");
    string submit(n, '0');
 
    deque<ti> segs;
    for (auto &[x, y, i] : initial_segs)
    {
        segs.emplace_back(x, y, i);
    }
 
    while (szz(segs))
    {
        auto [x, y, i] = segs.front();
        segs.pop_front();

        if (x > y) continue;

        if (x == y)
        {
            if(i == 1) {
            submit[x] = '1';
            } else {
                if (query_seg(x, x)) {
                    submit[x] = '1';
                }
            }
            continue;
        }
 
        int len = y - x + 1;
        int m = (i ? opt2[len] : opt[len]);
        debug("opt[%d][%d]=%d\n", i, len, (i ? opt2[len] : opt[len]));

        pii lsg(x, x + m - 1), rsg(x + m, y);
        
        if (query_seg(lsg)) {
            segs.emplace_back(lsg.va, lsg.vb, 1);
            segs.emplace_back(rsg.va, rsg.vb, 0);
        } else {
            segs.emplace_back(rsg.va, rsg.vb, i);
        }
    }
 
    debug("lqnt = %d\n", lqnt);
    answer(submit);
}
 
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);
        debug("thres: %.3Lf", score.lower_bound(p - 1e-7)->vb);
    }
}

Compilation message

Main.cpp: In function 'int query_seg(int, int)':
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:179:5: note: in expansion of macro 'debug'
  179 |     debug("qseg %d %d\n", i, j);
      |     ^~~~~
Main.cpp: In function 'void init()':
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:252:37: note: in expansion of macro 'debug'
  252 |         for(int i = 0; i <= n; i++) debug("pows[%d] = %.6Lf\n", i, pows[i]);
      |                                     ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:254:13: note: in expansion of macro 'debug'
  254 |             debug("dp[%d] = %.3Lf (opt=%d), dp2[%d] = %.3Lf (opt2=%d)\n", i, dp[i], opt[i], i, dp2[i], opt2[i]);
      |             ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:256:9: note: in expansion of macro 'debug'
  256 |         debug("dp[%d] = %.3Le\n", n, dp[n]);
      |         ^~~~~
Main.cpp: In function 'void run()':
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:284:5: note: in expansion of macro 'debug'
  284 |     debug("================\n");
      |     ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:314:9: note: in expansion of macro 'debug'
  314 |         debug("opt[%d][%d]=%d\n", i, len, (i ? opt2[len] : opt[len]));
      |         ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:326:5: note: in expansion of macro 'debug'
  326 |     debug("lqnt = %d\n", lqnt);
      |     ^~~~~
Main.cpp: In function 'int main()':
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:346:9: note: in expansion of macro 'debug'
  346 |         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:347:9: note: in expansion of macro 'debug'
  347 |         debug("max query: %d\n", mqnt);
      |         ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
  106 | #define debug(...) 42
      |                    ^~
Main.cpp:348:9: note: in expansion of macro 'debug'
  348 |         debug("thres: %.3Lf", score.lower_bound(p - 1e-7)->vb);
      |         ^~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #1
10.0 / 10.0

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

Subtask #2
34.820000001 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 344 KB Output is correct (P=0.001, F=15.1, Q=17.5) -> 55.02 points
2 Correct 143 ms 344 KB Output is correct (P=0.005256, F=51.1, Q=69.1) -> 37.36 points
3 Correct 299 ms 344 KB Output is correct (P=0.011546, F=94.9, Q=132.5) -> 34.82 points
4 Correct 508 ms 344 KB Output is correct (P=0.028545, F=191.5, Q=258.5) -> 37.51 points
5 Correct 689 ms 344 KB Output is correct (P=0.039856, F=246.3, Q=322.6) -> 40.19 points
6 Correct 934 ms 344 KB Output is correct (P=0.068648, F=366.2, Q=463.6) -> 43.61 points
7 Correct 1145 ms 344 KB Output is correct (P=0.104571, F=490.3, Q=590.0) -> 49.63 points
8 Correct 1542 ms 344 KB Output is correct (P=0.158765, F=639.1, Q=760.0) -> 51.23 points
9 Correct 1837 ms 344 KB Output is correct (P=0.2, F=731.4, Q=874.4) -> 50.50 points