Submission #1034309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034309		ainta	COVID tests (CEOI24_covid)	C++17	0 / 100	1801 ms	600 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';

    printf("Q %s\n", mask_str.c_str());
    fflush(stdout);
	if(!DEBUG){
		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);
		}
	}
}
std::vector<bool> find_positive() {
	answer.resize(N);
	mask.resize(N);
	rep(i,N)answer[i]=0;
	int s = 0;
	if(P > 0.02 || 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 q = pow(1-P,j);
			double p = 1-q;
			double s = 1 + q * D[i-j] + p * (1 + D[j] + D[i-j]);
			if(D[i]>s){
				Path[i] = j;
				D[i]=s;
			}
		}
	}

    // 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);
		}
    }

//	printf("%f\n",(double)cnt/T);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'std::vector<bool> find_positive()':
Main.cpp:112:6: warning: unused variable 's' [-Wunused-variable]
  112 |  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:131:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     scanf("%d %lf %d", &N, &P, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:170:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |    scanf(" %c", &verdict);
      |    ~~~~~^~~~~~~~~~~~~~~~~

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