// 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;
int cnt[10005];
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;
cnt[j - i + 1]++;
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[2][10005]; // 0 : (1-q^i)Ki, 1 : Ui
int opt[2][10005];
vector<int> fib({1, 2});
lf pows[10005] = {1.0};
vector<ti> initial_segs;
void init()
{
if (t > 1 && initial_segs.empty())
{
while(fib.back() < n) fib.push_back(fib[szz(fib) - 2] + fib[szz(fib) - 1]);
for (int i = 1; i <= n; i++)
pows[i] = pow(1.0L - p, i);
dp[1][1] = 1.L;
for (int i = 2; i <= n; i++)
{
dp[0][i] = 100.L * i;
for(int j = 1; j < i; j++) {
if (!bs(all(fib), j)) continue;
lf pdp = 1.L - pows[i] + (1.L - pows[j]) * dp[1][i - j] + pows[j] * dp[0][i - j] + dp[0][j];
if(pdp < dp[0][i]) {
dp[0][i] = pdp;
opt[0][i] = j;
}
if (pdp < dp[0][i] + 0.5) {
debug("dp[0][%d] = %.3Lf <- pdp[%d] = %.3Lf\n", i, dp[0][i], j, pdp);
}
}
dp[1][i] = 100.L * i;
// don't know -> dp
for(int j = 1; j <= i; j++) {
if (!bs(all(fib), j) && j < i) continue;
// dp[i] * q^i
lf pdp = 1.L + dp[0][j] + dp[1][i - j];
if (pdp < dp[1][i]) {
dp[1][i] = pdp;
opt[1][i] = j;
}
if (pdp < dp[1][i] + 0.5) {
debug("dp[1][%d] = %.3Lf <- pdp[%d] = %.3Lf\n", i, dp[1][i], j, pdp);
}
}
}
for(int i = 1; i <= n; i++) {
debug("opt[0][%d] = %d, opt[1][%d] = %d\n", i, opt[0][i], i, opt[1][i]);
}
initial_segs.emplace_back(0, n-1, 1);
}
#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 == 0) {
submit[x] = '1';
} else {
if (query_seg(x, x)) {
submit[x] = '1';
}
}
continue;
}
int len = y - x + 1;
int m = opt[i][len];
pii lsg(x, x + m - 1), rsg(x + m, y);
if (query_seg(lsg)) {
segs.emplace_back(lsg.va, lsg.vb, 0);
segs.emplace_back(rsg.va, rsg.vb, 1);
} 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);
for(int i = 1; i <= n; i++) {
if (cnt[i]) {
debug("query(%d): %.3Lf\n", i, lf(cnt[i]) / qnt);
}
}
}
}
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:180:5: note: in expansion of macro 'debug'
180 | 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:246:21: note: in expansion of macro 'debug'
246 | debug("dp[0][%d] = %.3Lf <- pdp[%d] = %.3Lf\n", i, dp[0][i], j, pdp);
| ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
106 | #define debug(...) 42
| ^~
Main.cpp:262:21: note: in expansion of macro 'debug'
262 | debug("dp[1][%d] = %.3Lf <- pdp[%d] = %.3Lf\n", i, dp[1][i], j, pdp);
| ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
106 | #define debug(...) 42
| ^~
Main.cpp:269:13: note: in expansion of macro 'debug'
269 | debug("opt[0][%d] = %d, opt[1][%d] = %d\n", i, opt[0][i], i, opt[1][i]);
| ^~~~~
Main.cpp: In function 'void run()':
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
106 | #define debug(...) 42
| ^~
Main.cpp:297:5: note: in expansion of macro 'debug'
297 | debug("================\n");
| ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
106 | #define debug(...) 42
| ^~
Main.cpp:338:5: note: in expansion of macro 'debug'
338 | 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:358:9: note: in expansion of macro 'debug'
358 | 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:359:9: note: in expansion of macro 'debug'
359 | debug("max query: %d\n", mqnt);
| ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
106 | #define debug(...) 42
| ^~
Main.cpp:360:9: note: in expansion of macro 'debug'
360 | debug("thres: %.3Lf", score.lower_bound(p - 1e-7)->vb);
| ^~~~~
Main.cpp:106:20: warning: statement has no effect [-Wunused-value]
106 | #define debug(...) 42
| ^~
Main.cpp:363:17: note: in expansion of macro 'debug'
363 | debug("query(%d): %.3Lf\n", i, lf(cnt[i]) / qnt);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
344 KB |
Output is correct |
| 3 |
Correct |
5 ms |
344 KB |
Output is correct |
| 4 |
Correct |
6 ms |
344 KB |
Output is correct |
| 5 |
Correct |
5 ms |
344 KB |
Output is correct |
| 6 |
Correct |
5 ms |
344 KB |
Output is correct |
| 7 |
Correct |
6 ms |
340 KB |
Output is correct |
| 8 |
Correct |
6 ms |
344 KB |
Output is correct |
| 9 |
Correct |
5 ms |
344 KB |
Output is correct |
| 10 |
Correct |
3 ms |
344 KB |
Output is correct |
| 11 |
Correct |
4 ms |
344 KB |
Output is correct |
| 12 |
Correct |
5 ms |
344 KB |
Output is correct |
| 13 |
Correct |
3 ms |
344 KB |
Output is correct |
| 14 |
Correct |
6 ms |
344 KB |
Output is correct |
| 15 |
Correct |
5 ms |
344 KB |
Output is correct |
| 16 |
Correct |
4 ms |
344 KB |
Output is correct |
| 17 |
Correct |
5 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
344 KB |
Output is correct (P=0.001, F=15.1, Q=13.2) -> 90.00 points |
| 2 |
Correct |
124 ms |
344 KB |
Output is correct (P=0.005256, F=51.1, Q=56.0) -> 65.05 points |
| 3 |
Correct |
216 ms |
344 KB |
Output is correct (P=0.011546, F=94.9, Q=106.5) -> 60.45 points |
| 4 |
Correct |
428 ms |
344 KB |
Output is correct (P=0.028545, F=191.5, Q=214.2) -> 61.05 points |
| 5 |
Correct |
501 ms |
344 KB |
Output is correct (P=0.039856, F=246.3, Q=273.3) -> 62.57 points |
| 6 |
Correct |
764 ms |
344 KB |
Output is correct (P=0.068648, F=366.2, Q=398.8) -> 66.37 points |
| 7 |
Correct |
992 ms |
344 KB |
Output is correct (P=0.104571, F=490.3, Q=523.0) -> 71.05 points |
| 8 |
Correct |
1262 ms |
344 KB |
Output is correct (P=0.158765, F=639.1, Q=664.1) -> 77.82 points |
| 9 |
Correct |
1490 ms |
344 KB |
Output is correct (P=0.2, F=731.4, Q=750.0) -> 81.69 points |
