// Author: Jiří Kalvoda
#include <vector>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string>
using namespace std;
bool test_pupils(vector<int>) ;
const int NMAX = 112345;
int opt_ask[NMAX][2]; // Počet lidí; Zda víme existenci alespoň jednoho pozitivního
double opt_val[NMAX][2];
void f(vector<int> & out, int start, int len, bool exist)
{
//fprintf(stderr, "start: %d len: %d exist: %d\n", start, len, exist);
if(len < 1) return;
if(len == 1 && exist)
{
out.push_back(start);
return;
}
vector<int> ask;
int test_len = opt_ask[len][exist];
for(int i=0;i<test_len;i++) ask.push_back(i+start);
//fprintf(stderr,"test_len: %d\n", test_len);
if(test_pupils(ask))
{
f(out, start, test_len, 1);
f(out, start+test_len, len-test_len, 0);
}
else
f(out, start+test_len, len-test_len, exist);
}
vector<int> test(int n, double p) {
//for(int len=0;len<=n;len++) fprintf(stderr, "%lf->%d %lf->%d\n", opt_val[len][0], opt_ask[len][0], opt_val[len][1], opt_ask[len][1]);
fprintf(stderr, "Except: %lf\n", opt_val[n][0]);
fprintf(stderr, "p = %lf\n", p);
vector<int> ans;
f(ans, 0, n, 0);
return ans;
}
int n;
bool test_pupils(vector<int> pupils)
{
string out(n, '0');
for(int it : pupils)
out[it]='1';
printf("Q %s\n", out.c_str());
fflush(stdout);
char in;
scanf(" %c", &in);
return in=='P';
}
int main()
{
double p;
int t;
scanf("%d%lf%d", &n, &p, &t);
opt_val[0][0] = opt_val[0][1] = 0;
opt_val[1][0] = 1;
opt_val[1][1] = 0;
opt_ask[1][0] = 1;
opt_ask[1][1] = 1;
for(int len=2;len<=n;len++)
for(int exist=2; exist-->0;)
{
opt_val[len][exist] = NMAX;
for(int test_len=1;test_len<=(len-exist);test_len++)
{
double pr = 1-pow(1-p, test_len);
if(exist)
{
pr /= 1-pow(1-p, len);
}
double v = 1 +
pr * (opt_val[test_len][1] + opt_val[len-test_len][0]) +
(1-pr) * opt_val[len-test_len][exist];
if(v < opt_val[len][exist])
{
opt_ask[len][exist] = test_len;
opt_val[len][exist] = v;
}
}
}
for(int ti=0; ti<t; ti++)
{
auto positive = test(n, p);
{
string out(n, '0');
for(int it : positive)
out[it]='1';
printf("A %s\n", out.c_str());
fflush(stdout);
char in;
scanf(" %c", &in);
if(in != 'C') return 0;
}
}
return 0;
}
Compilation message
Main.cpp: In function 'bool test_pupils(std::vector<int>)':
Main.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf(" %c", &in);
| ~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d%lf%d", &n, &p, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | scanf(" %c", &in);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
596 KB |
Output is correct |
| 2 |
Correct |
42 ms |
592 KB |
Output is correct |
| 3 |
Correct |
53 ms |
688 KB |
Output is correct |
| 4 |
Correct |
43 ms |
816 KB |
Output is correct |
| 5 |
Correct |
54 ms |
728 KB |
Output is correct |
| 6 |
Correct |
50 ms |
440 KB |
Output is correct |
| 7 |
Correct |
47 ms |
592 KB |
Output is correct |
| 8 |
Correct |
32 ms |
492 KB |
Output is correct |
| 9 |
Correct |
38 ms |
436 KB |
Output is correct |
| 10 |
Correct |
27 ms |
468 KB |
Output is correct |
| 11 |
Correct |
30 ms |
476 KB |
Output is correct |
| 12 |
Correct |
30 ms |
848 KB |
Output is correct |
| 13 |
Correct |
31 ms |
592 KB |
Output is correct |
| 14 |
Correct |
34 ms |
588 KB |
Output is correct |
| 15 |
Correct |
28 ms |
476 KB |
Output is correct |
| 16 |
Correct |
16 ms |
848 KB |
Output is correct |
| 17 |
Correct |
17 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
480 KB |
Output is correct (P=0.001, F=15.1, Q=13.2) -> 90.00 points |
| 2 |
Correct |
122 ms |
472 KB |
Output is correct (P=0.005256, F=51.1, Q=55.9) -> 65.42 points |
| 3 |
Correct |
288 ms |
460 KB |
Output is correct (P=0.011546, F=94.9, Q=106.6) -> 60.28 points |
| 4 |
Correct |
486 ms |
460 KB |
Output is correct (P=0.028545, F=191.5, Q=214.2) -> 61.05 points |
| 5 |
Correct |
657 ms |
460 KB |
Output is correct (P=0.039856, F=246.3, Q=273.3) -> 62.57 points |
| 6 |
Correct |
940 ms |
472 KB |
Output is correct (P=0.068648, F=366.2, Q=398.8) -> 66.37 points |
| 7 |
Correct |
1252 ms |
464 KB |
Output is correct (P=0.104571, F=490.3, Q=523.0) -> 71.05 points |
| 8 |
Correct |
1515 ms |
608 KB |
Output is correct (P=0.158765, F=639.1, Q=664.1) -> 77.82 points |
| 9 |
Correct |
1507 ms |
500 KB |
Output is correct (P=0.2, F=731.4, Q=750.5) -> 81.49 points |
