Submission #1034963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034963		ainta	COVID tests (CEOI24_covid)	C++17	70.45 / 100	1851 ms	1048576 KiB

Main

#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 (stderr)

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);
      |    ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 60.450000003 / 90