| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1034963 |
2024-07-26T00:53:31 Z |
ainta |
COVID tests (CEOI24_covid) |
C++17 |
|
1851 ms |
1048576 KB |
#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], D2[1010];
int P1[1010], P2[1010];
void Go2(int b, int e);
void Go(int b, int e){
if(b==e){
answer[b]=1;
return;
}
int N = e-b+1;
if(P1[N]>0){
int c = P1[N];
if(test_range(b,b+c-1)){
Go(b,b+c-1);
Go2(b+c,e);
}
else{
Go(b+c,e);
}
}
else{
rng(i,b,e){
if(test_range(i,i))answer[i]=1;
}
}
}
void Go2(int b, int e){
if(b==e){
if(test_range(b,b))answer[b]=1;
return;
}
int N = e-b+1;
if(P2[N]>8e8){
if(test_range(b,e)){
Go(b,e);
}
return;
}
if(P2[N]>0){
int c = P2[N];
Go2(b,b+c-1);
Go2(b+c,e);
}
else if(P2[N]<0){
int c = -P2[N];
if(test_range(b,b+c-1)){
Go(b,b+c-1);
Go2(b+c,e);
}
else{
Go2(b+c,e);
}
}
else{
rng(i,b,e){
if(test_range(i,i))answer[i]=1;
}
}
}
int T;
std::vector<bool> find_positive() {
answer.resize(N);
mask.resize(N);
rep(i,N)answer[i]=0;
if(T==1){
rep(i,N)answer[i] = test_range(i,i);
return answer;
}
Go2(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() {
scanf("%d %lf %d", &N, &P, &T);
D[1] = 0;
D2[1] = 1;
rng(i,2,N){
D2[i]=D[i]=i;
P1[i]=P2[i]=i;
rng(j,1,i-1){
double p = (1-pow(1-P,j)) / (1-pow(1-P,i));
double q = 1-p;
double t2 = q * (1+D[i-j]) + p * (1 + D[j] + D2[i-j]);
double t3 = D2[j]+D2[i-j];
double t4 = q * (1+D2[i-j]) + p * (1 + D[j] + D2[i-j]);
if(D[i] > t2){
D[i] = t2;
P1[i] = j;
}
if(D2[i] > t3){
D2[i] = t3;
P2[i] = j;
}
if(D2[i] > t4){
D2[i] = t4;
P2[i] = -j;
}
}
double z = (1-pow(1-P,i))* D[i]+1;
if(D2[i] > z){
D2[i] = z;
P2[i] = 1e9;
}
}
/*printf("%f\n",D2[N]);
return 0;*/
// 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: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:174:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
174 | scanf("%d %lf %d", &N, &P, &T);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:233:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
233 | scanf(" %c", &verdict);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
523 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
344 KB |
Output is correct |
| 2 |
Correct |
33 ms |
344 KB |
Output is correct |
| 3 |
Correct |
37 ms |
344 KB |
Output is correct |
| 4 |
Correct |
32 ms |
344 KB |
Output is correct |
| 5 |
Correct |
35 ms |
344 KB |
Output is correct |
| 6 |
Correct |
38 ms |
344 KB |
Output is correct |
| 7 |
Correct |
26 ms |
460 KB |
Output is correct |
| 8 |
Correct |
24 ms |
464 KB |
Output is correct |
| 9 |
Correct |
32 ms |
344 KB |
Output is correct |
| 10 |
Correct |
23 ms |
344 KB |
Output is correct |
| 11 |
Correct |
23 ms |
344 KB |
Output is correct |
| 12 |
Correct |
23 ms |
344 KB |
Output is correct |
| 13 |
Correct |
24 ms |
344 KB |
Output is correct |
| 14 |
Correct |
23 ms |
344 KB |
Output is correct |
| 15 |
Correct |
23 ms |
344 KB |
Output is correct |
| 16 |
Correct |
14 ms |
344 KB |
Output is correct |
| 17 |
Correct |
18 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
344 KB |
Output is correct (P=0.001, F=15.1, Q=13.2) -> 90.00 points |
| 2 |
Correct |
172 ms |
456 KB |
Output is correct (P=0.005256, F=51.1, Q=55.9) -> 65.42 points |
| 3 |
Correct |
277 ms |
356 KB |
Output is correct (P=0.011546, F=94.9, Q=106.5) -> 60.45 points |
| 4 |
Correct |
557 ms |
344 KB |
Output is correct (P=0.028545, F=191.5, Q=213.9) -> 61.31 points |
| 5 |
Correct |
724 ms |
344 KB |
Output is correct (P=0.039856, F=246.3, Q=273.3) -> 62.57 points |
| 6 |
Correct |
1052 ms |
344 KB |
Output is correct (P=0.068648, F=366.2, Q=398.8) -> 66.37 points |
| 7 |
Correct |
1360 ms |
344 KB |
Output is correct (P=0.104571, F=490.3, Q=523.0) -> 71.05 points |
| 8 |
Correct |
1779 ms |
344 KB |
Output is correct (P=0.158765, F=639.1, Q=664.1) -> 77.82 points |
| 9 |
Correct |
1851 ms |
456 KB |
Output is correct (P=0.2, F=731.4, Q=750.5) -> 81.49 points |
