#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
/// You may use:
// The number of students
int N;
// The probability any given student is positive
double P;
int DEBUG = 0;
// This function performs a test on a subset of samples.
// Its argument is a vector of Booleans of length N,
// where the i-th element is true if the i-th sample should be added to the mix.
// It returns true if (and only if) at least one of the samples in the mix is positive.
int Z[1010];
int cnt=0;
bool test_students(std::vector<bool> mask) {
cnt++;
assert(mask.size() == (size_t)N);
std::string mask_str(N, ' ');
for (int i = 0; i < N; i++)
mask_str[i] = mask[i] ? '1' : '0';
if(!DEBUG){
printf("Q %s\n", mask_str.c_str());
fflush(stdout);
char answer;
scanf(" %c", &answer);
return answer == 'P';
}
int ss=0;
rep(i,N){
if(mask[i]) ss|=Z[i];
}
return ss;
}
std::vector<bool>answer, mask;
bool test_range(int b, int e){
rep(i,N)mask[i]=0;
rng(i,b,e)mask[i]=1;
return test_students(mask);
}
/// You should implement:
// This function will be called once for each test instance.
// It should use test_students to determine which samples are positive.
// It must return a vector of Booleans of length N,
// where the i-th element is true if and only if the i-th sample is positive.
double D[1010];
int Path[1010];
void Go(int b, int e){
if(b==e){
answer[b]=1;
return;
}
int N = e-b+1;
if(Path[N]){
int c = Path[N];
if(test_range(b,b+c-1)){
Go(b,b+c-1);
if(test_range(b+c,e)) Go(b+c,e);
}
else{
Go(b+c,e);
}
}
else{
rng(i,b,e){
if(test_range(i,i))answer[i]=1;
}
}
}
std::vector<bool> find_positive() {
answer.resize(N);
mask.resize(N);
rep(i,N)answer[i]=0;
int s = 0;
if(test_range(0,N-1)){
Go(0,N-1);
}
return answer;
}
ll rand_int(ll l, ll r) { //[l, r]
#ifdef LOCAL
static mt19937_64 gen;
#else
static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
#endif
return uniform_int_distribution<ll>(l, r)(gen);
}
int main() {
int T;
scanf("%d %lf %d", &N, &P, &T);
rng(i,2,N){
D[i]=i;
Path[i] = 0;
rng(j,1,i-1){
double p = (1-pow(1-P,j)) / (1-pow(1-P,i));
double q = 1-p;
double s = q * (1+D[i-j]) + p * (2 + D[j] + (1-pow(1-P,i-j)) * D[i-j] );
if(D[i]>s){
Path[i] = j;
D[i]=s;
}
}
//printf("%d %f\n",i,D[i]);
}
// You may perform any extra initialization here.
for (int i = 0; i < T; i++) {
if(DEBUG){
rep(j,N){
if(rand_int(0,999) < P*1000){
Z[j]=1;
}
else Z[j]=0;
}
}
std::vector<bool> answer = find_positive();
assert(answer.size() == (size_t)N);
std::string answer_str(N, ' ');
for (int j = 0; j < N; j++)
answer_str[j] = answer[j] ? '1' : '0';
if(!DEBUG){
printf("A %s\n", answer_str.c_str());
fflush(stdout);
char verdict;
scanf(" %c", &verdict);
if (verdict == 'W')
exit(0);
}
}
if(DEBUG)printf("%f\n",(double)cnt/T);
return 0;
}
Compilation message
Main.cpp: In function 'bool test_students(std::vector<bool>)':
Main.cpp:57:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
57 | for (int i = 0; i < N; i++)
| ^~~
Main.cpp:60:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
60 | if(!DEBUG){
| ^~
Main.cpp: In function 'std::vector<bool> find_positive()':
Main.cpp:117:6: warning: unused variable 's' [-Wunused-variable]
117 | int s = 0;
| ^
Main.cpp: In function 'bool test_students(std::vector<bool>)':
Main.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf(" %c", &answer);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | scanf("%d %lf %d", &N, &P, &T);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:176:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
176 | scanf(" %c", &verdict);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
344 KB |
Output is correct |
| 2 |
Correct |
47 ms |
344 KB |
Output is correct |
| 3 |
Correct |
45 ms |
340 KB |
Output is correct |
| 4 |
Correct |
43 ms |
344 KB |
Output is correct |
| 5 |
Correct |
45 ms |
428 KB |
Output is correct |
| 6 |
Correct |
56 ms |
428 KB |
Output is correct |
| 7 |
Correct |
34 ms |
344 KB |
Output is correct |
| 8 |
Correct |
29 ms |
344 KB |
Output is correct |
| 9 |
Correct |
40 ms |
344 KB |
Output is correct |
| 10 |
Correct |
28 ms |
344 KB |
Output is correct |
| 11 |
Correct |
33 ms |
452 KB |
Output is correct |
| 12 |
Correct |
33 ms |
452 KB |
Output is correct |
| 13 |
Correct |
31 ms |
444 KB |
Output is correct |
| 14 |
Correct |
33 ms |
344 KB |
Output is correct |
| 15 |
Correct |
31 ms |
344 KB |
Output is correct |
| 16 |
Correct |
19 ms |
604 KB |
Output is correct |
| 17 |
Correct |
16 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
444 KB |
Output is correct (P=0.001, F=15.1, Q=13.2) -> 90.00 points |
| 2 |
Correct |
166 ms |
344 KB |
Output is correct (P=0.005256, F=51.1, Q=58.5) -> 56.99 points |
| 3 |
Correct |
319 ms |
344 KB |
Output is correct (P=0.011546, F=94.9, Q=113.7) -> 50.21 points |
| 4 |
Correct |
576 ms |
344 KB |
Output is correct (P=0.028545, F=191.5, Q=232.5) -> 48.48 points |
| 5 |
Correct |
721 ms |
344 KB |
Output is correct (P=0.039856, F=246.3, Q=300.5) -> 47.87 points |
| 6 |
Correct |
1042 ms |
344 KB |
Output is correct (P=0.068648, F=366.2, Q=445.5) -> 48.23 points |
| 7 |
Correct |
1408 ms |
344 KB |
Output is correct (P=0.104571, F=490.3, Q=595.4) -> 48.45 points |
| 8 |
Correct |
1920 ms |
344 KB |
Output is correct (P=0.158765, F=639.1, Q=777.7) -> 48.19 points |
| 9 |
Correct |
2025 ms |
344 KB |
Output is correct (P=0.2, F=731.4, Q=903.7) -> 46.34 points |
