// 人外有人，天外有天
// 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 = 190;
} else if (abs(P - 0.011546) <= err) {
R = 86;
} else if (abs(P - 0.028545) <= err) {
R = 35;
} else if (abs(P - 0.039856) <= err) {
R = 25;
} else if (abs(P - 0.068648) <= err) {
R = 14;
} else if (abs(P - 0.104571) <= err) {
R = 9;
} else if (abs(P - 0.158765) <= err) {
R = 6;
} else if (abs(P - 0.2) <= err) {
R = 5;
}
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)
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:174:10: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
174 | int main() {
| ^
Main.cpp:174:10: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
Main.cpp:174:10: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:174: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:182:27: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
182 | assert(ans.size() == N);
| ~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
7030 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 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 |
8 ms |
344 KB |
Output is correct |
| 5 |
Correct |
8 ms |
344 KB |
Output is correct |
| 6 |
Correct |
7 ms |
596 KB |
Output is correct |
| 7 |
Correct |
7 ms |
344 KB |
Output is correct |
| 8 |
Correct |
7 ms |
340 KB |
Output is correct |
| 9 |
Correct |
8 ms |
344 KB |
Output is correct |
| 10 |
Correct |
10 ms |
344 KB |
Output is correct |
| 11 |
Correct |
9 ms |
344 KB |
Output is correct |
| 12 |
Correct |
8 ms |
344 KB |
Output is correct |
| 13 |
Correct |
7 ms |
344 KB |
Output is correct |
| 14 |
Correct |
7 ms |
344 KB |
Output is correct |
| 15 |
Correct |
9 ms |
344 KB |
Output is correct |
| 16 |
Correct |
7 ms |
344 KB |
Output is correct |
| 17 |
Correct |
10 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
344 KB |
Output is correct (P=0.001, F=15.1, Q=17.5) -> 55.02 points |
| 2 |
Correct |
221 ms |
344 KB |
Output is correct (P=0.005256, F=51.1, Q=74.6) -> 31.70 points |
| 3 |
Correct |
398 ms |
344 KB |
Output is correct (P=0.011546, F=94.9, Q=139.2) -> 31.39 points |
| 4 |
Correct |
762 ms |
344 KB |
Output is correct (P=0.028545, F=191.5, Q=272.5) -> 33.43 points |
| 5 |
Correct |
1008 ms |
344 KB |
Output is correct (P=0.039856, F=246.3, Q=350.9) -> 33.35 points |
| 6 |
Correct |
1355 ms |
344 KB |
Output is correct (P=0.068648, F=366.2, Q=497.6) -> 36.96 points |
| 7 |
Correct |
1608 ms |
344 KB |
Output is correct (P=0.104571, F=490.3, Q=636.3) -> 41.08 points |
| 8 |
Correct |
2126 ms |
344 KB |
Output is correct (P=0.158765, F=639.1, Q=796.0) -> 45.41 points |
| 9 |
Correct |
2523 ms |
344 KB |
Output is correct (P=0.2, F=731.4, Q=884.1) -> 49.04 points |
